开发者

Context free grammar?

开发者 https://www.devze.com 2022-12-27 06:23 出处:网络
I have this problem where I need to convert the following CFG to CFG in CNF. S-> ABa A-> aab B-> Ac

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 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.

  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
    


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
0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号