Context free grammer

Posted by Evil on Stack Overflow See other posts from Stack Overflow or by Evil
Published on 2010-04-13T18:39:56Z Indexed on 2010/04/13 18:43 UTC
Read the original article Hit count: 418

Filed under:

Hello. I have this problem where i need to convert the following CFG to CFG in CNF.
S-> ABa A-> aab B-> Ac

I know the steps are as follows.

1) Remove epsilon transitions - Done 2) remove unit productions 3) convert to CNF by: 3.1] introduce a new non terminal for each term 3.2] replace terminals in the productions rules with the new nonterminal 3.3] introduce new nonterminals to reduce the length of the right side of each production

i'm a bit confused on how i would do that with the problem above. Mostly i am confused on step 2 and unit productions. If i could get some help or perhaps a link to a good tutorial that would be most helpful.

© Stack Overflow or respective owner

Related posts about cnf