computer-science - チョムスキー正規形 - 計算理論

Question

文法をチョムスキー標準形(CNF)に変更したいです。

これは例です

S--> AB | ɛ

A--> aASb | a

B--> bS

私はこれを解決しようとします

S --> [A] [B]

[A] --> [aA] [Sb] | [a]

[aA] --> [a] A

[Sb] --> s [b]

[a] --> a

[b] --> b

答えはわかりません。それが正しいか間違っているか誰か教えてもらえますか？

Answer 1

1 つの間違いは、S --> ɛトランジションを削除したことです。それが必要です (S --> ɛは CNF で明確に許可されていますが、許可されていAnyNonTerminalOtherThanS --> ɛません)。

次に、ルール[A] --> [a]は[A] --> a、RHS に項目が 1 つしかない場合、それが端末である必要があるためです。

[aA] --> [a] A
[Sb] --> s [b]

これら 2 つはタイプミスのようAでsあり、存在しません。あなたはおそらく次のことを意味していました：

[aA] --> [a] [A]
[Sb] --> [S] [b]

それ以外は、あなたが持っているものが正しいです。