Automata-theory-greibach-normal-form
提供：Dev Guides
グレイバッハ標準形
プロダクションが次の形式である場合、CFGはGreibach Normal形式です-
A→b
A→bD〜1〜…D〜n〜
S→ε
ここで、A、D〜1〜、….、D〜n〜は非端末であり、bは端末です。
CFGをGreibach正規形に変換するアルゴリズム
ステップ1 *-開始記号 *S が右側にある場合は、新しい開始記号* S ’と新しい制作 *S’→S を作成します。
- ステップ2 *-Nullプロダクションを削除します。 （前述のNull生成除去アルゴリズムを使用）
- ステップ3 *-ユニットプロダクションを削除します。 （前述のユニット生産除去アルゴリズムを使用）
- ステップ4 *-直接および間接の左再帰をすべて削除します。
- ステップ5 *-プロダクションを適切に置き換えて、適切な形式のGNFに変換します。
問題
次のCFGをCNFに変換します
S→XY | Xn | p
X→mX | m
Y→Xn | o
溶液
ここでは、 S はプロダクションの右側に表示されず、プロダクションルールセットにはユニットまたはヌルプロダクションがありません。 そのため、ステップ1からステップ3をスキップできます。
- ステップ4 *
交換後
XのS→XY | Xo | p
with
mX | m
私達は手に入れました
S→mXY | mY | mXo | mo | p。
交換後
X in Y→X〜n〜| 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
