グライバッハ標準形

プロダクションが次の形式の場合、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