Context free grammar?

1
votes

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.

2
grammarcontext-free-grammarchomsky-normal-form

2 Answers

0
votes

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
    1. replace terminals in the productions rules with the new nonterminal
    2. introduce new nonterminals to reduce the length of the right side of each production

Steps 1 and 2 are already complete. So we only need to worry about step 3.

Starting Grammar:

S-> ABa
A-> aab
B-> Ac

  1. Introduce a new non terminal for each term.

    S  -> ABa
A  -> aab
B  -> Ac
C  -> a
D  -> b
E  -> c

  2. Replace terminals in the productions rules with the new nonterminal.

    S  -> ABC
A  -> CCD
B  -> AE
C  -> a
D  -> b
E  -> c

  3. Introduce new nonterminals to reduce the length of the right side of each production. 

    S  -> AF
A  -> CG
B  -> AE
C  -> a
D  -> b
E  -> c
F  -> BC
G  -> CD
0
votes
S->ABa
C.N.F. is :
M->AB
Z->a
S->MZ

A->aab
C.N.F. is :
X->aa
Y->b
A->XY

B->Ac
C.N.F. is:
K->a
B->AK