complexity-theory - チョムスキー正規形変換アルゴリズム

Question

文法をチョムスキー標準形に変換したいときに、新しい開始状態 S0 -> S を追加するのはなぜですか? そうしないと何がうまくいかないのでしょうか？

最初はイプシロンの法則によるものだと思っていました。ただし、開始変数からイプシロン ルールを削除しません。では、S0 -> S を追加する利点は何ですか?

ありがとう

Answer 1

空の文字列が言語に含まれているかどうかに応じて、ルール $S --> \epsilon$ (または $S_0 --> \epsilon$) がある場合があります。これにより、ルールの右側に表示される可能性がある場合、任意の数のシンボル $S$ が削除される可能性があります。スタート シンボルを再び表示したくないため、新しいシンボルを導入します。

このようにして、ルール A -> BC の適用ごとに、正確に 1 つ多くのシンボルを取得します。

Answer 2

一応説明はあると思います。文法が次のような場合:

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

次に、特定の順序を考慮しないため、「ユニット規則」を削除するステップで、最初に S --> S1 を削除すると、次のようになります。

S1 --> S1
S1 --> a

開始変数は完全に削除されます。