# Grammar to Chomsky Normal Form

1. Nov 4, 2007

### MalickT

I have grammar:

S -> ASA
S -> aB
A -> B
A -> S
B -> b
B -> epsilon (empty string)

Can someone please help me to convert this grammar to Chomsky Normal From so i can do CKY-algorithm

2. Jul 19, 2008

### eburgos

Hi,

S -> ASA | aB
A -> B | S
B -> b | eps

S -> AS | SA | CB | a
A-> b | AS | SA | CB | a
B -> b
C -> a

3. Jul 14, 2010

### Altrix

Saw this online and decided to give another version, because I'm not sure if the answer above is correct. Unless there is a rule that allows ASA -> AS | SA that I don't know about.

(From where you left off...)
S -> ASA | aB
A -> B | S
B -> b | eps

(Step 1: remove eps productions)
S -> ASA | aB | a
A -> B | S
B -> b

(Step 2: remove unit productions)
S -> ASA | aB | a
A -> b | ASA | aB | a
B -> b

(Step 3: remove useless productions)
none, all have terminal variable

(Step 4: put into Chomsky form)
S -> DA | CB | a
A -> b | DA | CB | a
B -> b
C -> a
D -> AS

4. Jul 7, 2011

Can someone help me convert this Grammar to Chomsky Normal Form?

S--->XYx
X--->xxy
Y--->Xw

Thank you.

5. Jul 7, 2011

### aegrisomnia

6. Jun 14, 2012

### maram

help me in this
if we have E →E+T/E-T/T
T→T*F/T-F/F
F→(E)/i/ε
how we will solve using chomsky normal form