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.
- Remove epsilon transitions - Done
- remove unit productions
- convert to CNF by:
- introduce a new non terminal for each term
- replace terminals in the productions rules with the new nonterminal
- introduce new nonterminals to reduce the len开发者_开发问答gth 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.
I know the steps are as follows.
- Remove epsilon transitions - Done
- remove unit productions
- convert to CNF by: 1.introduce a new non terminal for each term
- replace terminals in the productions rules with the new nonterminal
- 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
Introduce a new non terminal for each term.
S -> ABa A -> aab B -> Ac C -> a D -> b E -> c
Replace terminals in the productions rules with the new nonterminal.
S -> ABC A -> CCD B -> AE C -> a D -> b E -> c
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
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
精彩评论