grammar - 文脈自由文法？

Question

次の CFG を CNF の CFG に変換する必要があるという問題があります。

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

手順は次のとおりです。

1. イプシロン遷移を削除 - 完了
2. ユニットプロダクションを削除
3. 次の方法で CNF に変換します。
   1. 学期ごとに新しい非端末を導入する
   2. 生産ルールの端末を新しい非端末に置き換えます
   3. 各プロダクションの右側の長さを減らすために新しい非終端記号を導入する

上記の問題でそれを行う方法について少し混乱しています。ほとんどの場合、ステップ 2 とユニット プロダクションで混乱しています。

Answer 1

手順は次のとおりです。

1. イプシロン遷移を削除 - 完了
2. ユニットプロダクションを削除
3. 次の方法で CNF に変換します。 1. 各用語に新しい非終端記号を導入
   1. 生産ルールの端末を新しい非端末に置き換えます
   2. 各プロダクションの右側の長さを減らすために新しい非終端記号を導入する

ステップ 1 と 2 はすでに完了しています。したがって、ステップ 3 についてのみ心配する必要があります。

開始文法:

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

1. タームごとに新しい非ターミナルを導入します。

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

2. プロダクション ルールのターミナルを新しい非ターミナルに置き換えます。

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

3. 各プロダクションの右側の長さを減らすために、新しい非終端記号を導入します。

   S  -> AF
   A  -> CG
   B  -> AE
   C  -> a
   D  -> b
   E  -> c
   F  -> BC
   G  -> CD
   

Answer 2

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