私はいくつかのテスト準備資料に取り組んでいて、この問題に固執しています。
L = {we {a、b} *：w = wRであり、すべてのaの直後にab}がある場合の文脈自由文法を表示します。
wRは逆にwです。したがって、英語では、すべての「a」の後に「b」が続く回文で、任意の数のaとbを使用します。
これまでのところ、逆の部分でこれを取得しましたが、回文のプロパティが保持されていることを確認しながら、すべてのaの後にabの部分を組み込む方法がわかりません。
S -> bSb | b | [the empty string]
どんな助けでも大歓迎です！
すべての "a" の後に "b" が続く必要があり、結果の単語は回文でなければならないため (最後から最初まで読んでも同じです)、これはすべての "a" の前にも a がなければならないことを意味します。 "b"。
中間から単語を構築し始め、両方向に成長します。ルールは、中間セクションが "a" で終わる (したがって始まる) 場合 (これは非終端の A です)、その後に "b" が続く (そして先行する) 必要があります。一方、中間セクションが "b" で囲まれている場合 (これは非終端 B です)、単一の "a" (前のケース) または任意の数の "b" で展開できます。真ん中の偶数の「b」の特殊なケースも処理されます。開始記号 S は、"b" で制限された単語のみを許可するため、すべてのルールが一致します。
S -> B | [empty]
B -> bAb | bBb | bb | b
A -> aBa | a
編集:以前の解決策は正しくありませんでした。これが機能することを願っています。