CODEWITHSUNDEEP
grammarcontext-free-grammarchomsky-normal-form
Evil
Evil

Reputation: 141

Context free grammar?

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.

Upvotes: 1

Views: 4280

Answers (2)

Suchita Achari
Suchita Achari

Reputation: 1

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

Upvotes: 0

Garrison
Garrison

Reputation: 386

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

Upvotes: 0

Related Questions