0

言語のプッシュダウン オートマトンの設計について質問があります。

L = { w in {a, b}* : 2n_a(w) <= n_b(w) <= 3n_a(w) }

つまり、 の の数は、bの2 倍と の 3 倍のw"間"です。aa

私はこの質問について混乱しています: 私は (願わくば!) の数がの数の 2 倍または の数の 3 倍にb等しい場合に言語を受け入れるように PDA を設計する方法を知っています (できれば!) 。aa

この言語はそれらの交差点のようですが、交差点を使用して PDA を作成する簡単な方法はないと思います。数値が 2 つの値の間にある可能性があるという事実をどのように組み込むことができるでしょうか。

どんな助けでも大歓迎です...

PS文脈自由文法（および説明）も提供していただけると、非常に役立ちます。

PPS: また、文脈自由文法を段階的に構築する方法を示すリンクを誰かが提供できる場合は、本当に必要です。（正規表現の通常の文法へのリンクを見つけましたが、文脈自由文法の場合、変数をたどろうとして、ある変数がそれ自体に行くか、別の変数に行き、それが最初の変数に戻るのを見ると、私は本当に混乱します。）

4

1 に答える 1

0

すべての a が 2 つの b または 3 つの b をプッシュするように、PDA を作成する必要があります。たとえば、3 つの a と 8 つの b を持つ文字列: 最初の a は 3 つの b をプッシュし、2 番目の a は 3 つの b をプッシュし、3 番目の a は 2 つの b をプッシュします。

この CFG はすべてのケースをカバーしていると思います: S -> aB|Ba|EOS B -> SbSbS|SbSbSbS

これは、すべての a に対して、2 つの b または 3 つの b があることを意味します。

https://www.youtube.com/watch?v=AbbZVvQkees これは、PDA の優れた YouTube チャンネルです。

于 2014-06-10T18:32:17.640 に答える