
December 6th, 2012, 10:31 AM
|
Registered User
|
|
Join Date: Dec 2012
Posts: 1
Time spent in forums: 15 m 53 sec
Reputation Power: 0
|
|
Convert CFG to CNF
Hi guys,
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| ^
B=> AS
The algorithm is as follows:
Eliminate ^-production
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.
Thank you
|