Automata-theory-cfg-simplification
CFGの簡素化
CFGでは、すべてのプロダクションルールとシンボルが文字列の派生に必要ではない場合があります。 その上、いくつかのヌル生産とユニット生産があるかもしれません。 これらのプロダクションとシンボルの削除は、* CFGの単純化*と呼ばれます。 簡素化は、基本的に次の手順で構成されます-
- CFGの削減
- ユニット生産の削除
- Nullプロダクションの削除
CFGの削減
CFGは2段階で削減されます-
フェーズ1 *-CFG *G からの同等の文法* G ’*の派生。各変数が何らかの終端文字列を派生します。
導出手順-
ステップ1-一部の端末を派生させ、 i = 1 を初期化するすべてのシンボル* W〜1〜*を含めます。
ステップ2-* W〜i〜を導出するすべてのシンボル W〜i + 1〜*を含めます。
ステップ3- i をインクリメントし、* W〜i + 1〜= W〜i〜*になるまでステップ2を繰り返します。
ステップ4-* W〜i〜*が含まれるすべてのプロダクションルールを含めます。
フェーズ2 *-CFGからの同等の文法 *G” の派生、* G ’*。各記号は文型で表示されます。
導出手順-
ステップ1-* Y〜1〜に開始記号を含め、 *i = 1 を初期化します。
ステップ2-* Y〜i〜から派生できるすべてのシンボル Y〜i + 1〜*を含め、適用されたすべての生産ルールを含めます。
ステップ3-* Y〜i + 1〜= Y〜i〜になるまで、 *i をインクリメントし、ステップ2を繰り返します。
問題
文法Gに相当する簡約された文法を見つけます。生成規則はPです。S→AC | B、A→a、C→c | BC、E→aA | e
溶液
- フェーズ1 *-
T = \ {a、c、e}
W〜1〜= \ {A、C、E}ルールA→a、C→cおよびE→aA
W〜2〜=ルールS→ACからの\ {A、C、E} U \ {S}
W〜3〜= \ {A、C、E、S} U∅
W〜2〜= W〜3〜なので、G ’を次のように導出できます-
G ’= \ {\ {A、C、E、S}、\ {a、c、e}、P、\ {S}}
ここで、P：S→AC、A→a、C→c、E→aA | e
- フェーズ2 *-
Y〜1〜= \ {S}
Y〜2〜=ルールS→ACからの\ {S、A、C}
Y〜3〜= \ {S、A、C、a、c}ルールA→aおよびC→c
Y〜4〜= \ {S、A、C、a、c}
Y〜3〜= Y〜4〜なので、G”を導出できます-
G” = \ {\ {A、C、S}、\ {a、c}、P、\ {S}}
ここで、P：S→AC、A→a、C→c
ユニット生産の削除
A→Bの形式の生産規則（A、B∈非終端）は、* unit production。*と呼ばれます。
取り外し手順-
ステップ1 *- *A→B を削除するには、文法で B→x が発生するたびに、生成規則 A→x を文法規則に追加します。 [x∈ターミナル、xはヌルにすることができます]
ステップ2 *-文法から *A→B を削除します。
- ステップ3 *-すべてのユニット生産が削除されるまで、ステップ1から繰り返します。
問題
次からユニット生産を削除します-
S→XY、X→a、Y→Z | b、Z→M、M→N、N→a
ソリューション-
文法には3つの単位生産があります-
Y→Z、Z→M、M→N
最初に、M→Nを削除します。
N→aとして、M→aを追加し、M→Nを削除します。
生産セットは
S→XY、X→a、Y→Z | b、Z→M、M→a、N→a
- Z→Mを削除します*
M→aとして、Z→aを追加し、Z→Mを削除します。
生産セットは
S→XY、X→a、Y→Z | b、Z→a、M→a、N→a
- Y→Zを削除します。*
Z→aとして、Y→aを追加し、Y→Zを削除します。
生産セットは
S→XY、X→a、Y→a | b、Z→a、M→a、N→a
これで、Z、M、およびNは到達不能になったため、それらを削除できます。
最終的なCFGはユニットの生産が無料です-
S→XY、X→a、Y→a | b
Nullプロダクションの削除
CFGでは、生産* A→ε*がある場合、または A で始まり、最終的に次で終わる派生が存在する場合、非終端記号 'A' はNULL可能変数です。
ε：A→…….…→ε
取り外し手順
- ステップ1 *-εを導出するnull許容の非終端変数を見つけます。
ステップ2 *-各プロダクション *A→a で、すべてのプロダクション A→x を構築します。ここで、 x は、ステップ1から1つまたは複数の非端末を削除することにより ‘a’ から取得されます。
- ステップ3 *-元の制作物をステップ2の結果と組み合わせ、*ε-制作物*を削除します。
問題
次からヌル生産を削除します-
S→ASA | aB | b、A→B、B→b | ∈
ソリューション-
2つのNULL可能変数があります- A および B
最初に、B→εを削除します。
- B→ε*を削除すると、生産セットは-
S→ASA | aB | b | a、AεB | b | ＆epsilon、B→b
- A→εを削除します。*
- A→ε*を削除すると、生産セットは-
S→ASA | aB | b | | SA | AS | S、A→B | b、B→b
これは、ヌルトランジションのない最終プロダクションセットです。
