チョムスキー標準形（CNF）に文法を変更したい。チョムスキー標準形 - 計算理論
これは私が答えについてわからないこの
S --> [A] [B]
[A] --> [aA] [Sb] | [a]
[aA] --> [a] A
[Sb] --> s [b]
[a] --> a
[b] --> b
を解決しようとする例
S--> AB | ɛ
A--> aASb | a
B--> bS
です。それが正しいか間違っているか誰にでも教えてもらえますか？
間違いの1つは、S --> ɛトランジションを削除したことです。 AnyNonTerminalOtherThanS --> ɛではありませんが、（S --> ɛがCNFで特に許可されている）必要があります。
この場合、RHSにアイテムが1つしかない場合は、端末でなければならないため、ルールは[A] --> aになります。
[aA] --> [a] A
[Sb] --> s [b]
これら二つはAとs存在していないとして、タイプミスのように見えます。おそらく：
[aA] --> [a] [A]
[Sb] --> [S] [b]
それ以外のものは正しいと思います。
@ sepp2k-ありがとうございました。 – cool
@ sepp2k-申し訳ありませんが、前に述べたように[A] - > [a]ルールは含まれていませんでした。私はあなたのポイントを持っていますが、RHS上に1つのアイテムしかない場合、それはターミナルでなければなりません。 – cool
@ sepp2K-こんにちは！私は、リクエストがあります。私はここで質問した。http://stackoverflow.com/questions/13143186/example-of-non-linear-unambiguous-and-non-deterministic-cfl - 疑いを晴らすことができます。 –
あなたの質問にはまったく適切なフォーラムではありません。ここに投稿してみてください：http://cstheory.stackexchange.com/ –
あなたの答えは空の単語を生成しません。 –
@Nico：絶対にそうではありません。 cstheoryは*研究レベル*の質問のサイトです。また、基本的なCSの質問は常にここで話題になっています。 – sepp2k