私はアルファベットの上に CFG を書き込もうとしていΣ = {a,b}ます.ab
これで、CFG、変数、プロダクション ルールなどの基本的な概念を理解できました。残念ながら、前述の CFG を作成するためのアイデアは尽きてしまいました。私がこれまでに持っているのは
S → aYXYa
X → XbX | b | λ
Y → ???
プロダクション ルールでは、両側に 2 つの ** **があり、真ん中に好きなだけ** **がある文字列が得られると思います。ただし、各側に正確に同じ数の ** ** があることを確認しながら、 ** ** の両側にできるだけ多くの ** ** を配置する方法がわかりません。SXababa
任意の提案、解決策をいただければ幸いです。ありがとう。
以前にこのクラスを教えた元教授として、私はあなたに答えを与えるつもりはありません. ただし、ヒントを提供します。
a と残りの 2 つの部分に分割するのは正しい考えです。ただし、どちらも正しく行っていません。
最初に書いてみてください: a n ba n そしてそこから分岐します。
それが役立つことを願っています。
S→aSa| B B→b| bB
これはあなたが探しているCFGでなければなりません。最初と最後で同じことを扱っているときはいつでも、同じ変数が同じ方法で入力されることを保証できないことに注意してください。そのため、それらを明示的にする必要があります。
私のCS学部時代からしばらく経ちましたが、これは合理的に見えます。
S-> aSa | bX
X-> bX | E
基本的には、Sから始めて、必要な数のaのペアを追加してから、Xに切り替えて、必要な数のbを追加します。