views:

51

answers:

1

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:
    1. introduce a new non terminal for each term
    2. replace terminals in the productions rules with the new nonterminal
    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.

A: 

It's been years since I did that kinda stuff. This paper [PDF] helped me out a lot.

aduric
that was very helpful. thank you :)
Evil