グライバッハ標準形
プロダクションが次の形式の場合、CFGはGreibach標準形になります-
A→b
A→BD 1 ... D n個
S→ε
ここで、A、D 1、....、D nは非終端記号であり、bは終端記号です。
CFGをグライバッハ標準形に変換するアルゴリズム
Step 1 −開始記号の場合 S 右側に発生し、新しい開始記号を作成します S’ と新しいプロダクション S’ → S。
Step 2−Nullプロダクションを削除します。（前述のヌル生成除去アルゴリズムを使用）
Step 3−ユニットプロダクションを削除します。（前述のユニット生産除去アルゴリズムを使用）
Step 4 −すべての直接および間接の左再帰を削除します。
Step 5 −プロダクションを適切に置き換えて、適切な形式のGNFに変換します。
問題
次のCFGをCNFに変換します
S→XY | Xn | p
X→mX | m
Y→Xn | o
解決
ここに、 Sプロダクションの右側には表示されず、プロダクションルールセットにユニットまたはヌルプロダクションはありません。したがって、ステップ1からステップ3をスキップできます。
Step 4
交換後
X inS→XY | Xo | p
と
mX | m
私達は手に入れました
S→mXY | mY | mXo | mo | p。
そして交換後
X inY→ Xn | o
の右側で
X→mX | m
私達は手に入れました
Y→mXn | mn | o。
2つの新しいプロダクションO→oとP→pがプロダクションセットに追加され、次のように最終的なGNFに到達しました。
S→mXY | mY | mXC | mC | p
X→mX | m
Y→mXD | mD | o
O→o
P→p