チョムスキー標準形変換アルゴリズム

なぜ文法をチョムスキー正規形に変換したいのですが、新しい開始状態S0 - > Sを追加するのですか？私たちがそれをしなければ何がうまくいかないのですか？チョムスキー標準形変換アルゴリズム

最初はイプシロンのルールのためだと思っていました。しかし、変数startからイプシロン規則を削除しません。だから、S0→Sを加えることのメリットは何ですか？

ありがとうございました

空の文字列が言語に含まれているかどうかによって、$ S→\ε$（または$ S_0→\ε$）という規則があるかもしれません。ルールの右側に$ S $があれば、任意の数の記号$ S $を削除することができます。開始シンボルが再び表示されないようにするため、新しいシンボルを導入します。

このようにして、ルールA-> BCのアプリケーションごとにまったく1つのシンボルが得られます。

2016-06-03 15:24:16

S ---> \ epsilonというルールを持っていても、その変数が開始記号でない場合にのみ、イプシロンルールが削除されるため、ルールは削除されないため、問題はないと思います。 –

ポイントは、CNFの場合、長さnの文字列の導出には、n-1の規則A→BCとnの形式がA→aであることがわかります。文脈S→A、A→AS、A→a、S→epsは任意の数の方法で文字列aを導出することができます。これはあなたが**通常のフォーム**から望むものではありません。 –

私はいくつかの説明があると思います。

： - ：文法はこのようであれば最初> S1と、私たちは持っているだろう、我々は特定の順序を考慮していないので、「単位ルール」を除去する工程で

S --> S1 
S1 --> S 
S1 --> a

その後、我々はSを除去することがあります

S1 --> S1 
S1 --> a

であり、開始変数は完全に削除されています。

2016-06-01 02:41:59

答えて