文脈自由文法を書くにはどうすればいいですか？

Question

私はと同じ番号で始まり、終わるすべての単語について、アルファベットのΣ = {a,b}にCFGを書こうとしています。中央には少なくとも1つのbがあります。

私はCFG、変数、生産ルールなどの基本的な概念を理解しています。残念ながら、私は前述のCFGを書くためのアイディアを使い果たしました。私がこれまで持っているすべては、私はプロダクションルールSとXはできるだけ多くしてくれ両側に2つの** a ** sの文字列を与えることを考える

S → aYXYa 
X → XbX | b | λ 
Y → ??? 

です** b **私は好きなように真ん中にいる。しかし、** b **の両側に** a **の数をどのように置くことができるのかよく分かりませんが、両側に** a **の数が正確に同じであることを確認しています。

どのような提案、解決策でも大歓迎です。ありがとう。

Answer 1

 
S → aSa | B 
B → b | bB 

これはあなたが探しているCFGである必要があります。最初と最後で同じことを扱ったときは、同じvarが同じ方法で満たされることを保証できないことに注意してください。したがって、あなたはそれらを明示的にする必要があります。

Answer 2

前にこのクラスを教えてくれた元教授のように、私はあなたに答えを与えるつもりはありません。しかし、私はあなたにヒントを与えるでしょう：

あなたは2つの部分、aとそれ以外の部分に分ける正しい考えがあります。しかし、あなたはどちらかを正しく実行していません。

最初に試してみてください：ⁿ ba ⁿそこから分岐します。

希望に役立ちます。

Answer 3

は、それは私のCS大学生の日以来、しばらくしているが、これは合理的になります。

S - > ASA | bX

X - > bX | E

基本的には、Sで始まり、必要な数だけaのペアを追加してから、Xに切り替えてbを必要な数だけ追加します。