Automata-theory-chomsky-normal-form
チョムスキー標準形
プロダクションが次の形式である場合、CFGはチョムスキー標準形です-
- A→a
- A→BC
- S→ε
ここで、A、B、およびCは非終端記号で、 a は終端記号です。
チョムスキー標準形に変換するアルゴリズム-
ステップ1 *-開始記号 *S が右側にある場合は、新しい開始記号* S ’と新しい制作 *S’→S を作成します。
- ステップ2 *-Nullプロダクションを削除します。 （前述のNull生成除去アルゴリズムを使用）
- ステップ3 *-ユニットプロダクションを削除します。 （前述のユニット生産除去アルゴリズムを使用）
ステップ4 *-各プロダクションを置き換えます A→B〜1〜…B〜n〜 where n> 2 with A→B〜1〜C where C→B〜2〜…B〜n〜 *。 右側に2つ以上のシンボルがあるすべての制作物に対してこの手順を繰り返します。
ステップ5 *-プロダクションの右側が *A→aB の形式であり、aが端末で、 A、B が非端末の場合、プロダクションは A→XB および*に置き換えられますX→a 。 *A→aB という形式のすべてのプロダクションに対してこの手順を繰り返します。
問題
次のCFGをCNFに変換します
S→ASA | aB、A→B | S、B→b | ε
溶液
（1） R.H.Sに S が表示されるため、新しい状態* S〜0〜を追加し、 *S〜0〜→S をプロダクションセットに追加して、
S〜0〜→S、S→ASA | aB、A→B | S、B→b | ∈
- （2）*ここで、nullプロダクションを削除します-
B→∈およびA→∈
B→εを削除すると、生産集合は-
S〜0〜→S、S→ASA | aB | a、A→B | S | ∈、B→b
A→εを削除すると、生産集合は-
S〜0〜→S、S→ASA | aB | | AS | SA | S、A→B | S、B→b
- （3）*次に、単位生産を削除します。
S→Sを削除すると、生産セットは-
S〜0〜→S、S→ASA | aB | | AS | SA、A→B | S、B→b
S〜0〜→Sを削除すると、生産セットは-
S〜0〜→ASA | aB | | AS | SA、S→ASA | aB | | AS | SA
A→B | S、B→b
A→Bを削除すると、プロダクションセットは-
S〜0〜→ASA | aB | | AS | SA、S→ASA | aB | | AS | SA
A→S | b
B→b
A→Sを削除すると、プロダクションセットは-
S〜0〜→ASA | aB | | AS | SA、S→ASA | aB | | AS | SA
A→b | ASA | aB | | AS | SA、B→b
- （4）*ここで、R.H.Sの3つ以上の変数を見つけます
ここでは、S〜0〜→ASA、S→ASA、A→ASAはR.H.S.の2つの非端末に違反しています。
したがって、ステップ4とステップ5を適用して、CNFにある次の最終製品セットを取得します-
S〜0〜→AX | aB | | AS | SA
S→AX | aB | | AS | SA
A→b | AX | aB | | AS | SA
B→b
X→SA
- （5）*プロダクションを変更する必要がありますS〜0〜→aB、S→aB、A→aB
そして、最終的な生産セットは-
S〜0〜→AX | YB | | AS | SA
S→AX | YB | | AS | SA
A→b A→b | AX | YB | | AS | SA
B→b
X→SA
Y→a
