December 6th, 2012, 10:31 AM
Join Date: Dec 2012
Time spent in forums: 15 m 53 sec
Reputation Power: 0
Convert CFG to CNF
I am a rookie in automaton theory.
Im trying to write a c++ program to convert Context Free Grammar to Chomsky Normal Form.
I am reading a file with CFG and converting it to CNF. I have read the content of the file but I am not sure how to use the algorithm to convert it to CNF.
The sample file will look like this. Here S, A and B are nonterminals and a and b are terminals and ^ represent the empty string.
S=> A | aB
A=> bB | aAa| ^
The algorithm is as follows:
Eliminate unit production
Eliminate useless symbols
Put in CNF form
Im trying to work this problem for weeks now Im getting really frustrated. Please help me with this.