Grammar to Chomsky Normal Form

[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

 

[eburgos]

Hi,

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

your CNF grammar should be

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

 

[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

 

[hammadhere10]

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

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

Thank you.
Urgent Reply Needed

 

[aegrisomnia]

That's probably not homework, right?

What precisely doesn't make sense about this?
http://en.wikipedia.org/wiki/Chomsky_normal_form

 

[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