automata - bよりも多くのaを含む文字列の言語を受け入れるPDA

Question

次の言語を認識するPDAを作成します：bよりも多くのaを含む文字列の言語

私はこの質問に数日間苦労してきました、私は完全な精神的ブロックにぶつかったようです。この問題をどのように解決できるかについて、誰かがガイダンスや指示を提供できるでしょうか？

Answer 1

「b よりも a の方が多い」という問題は、PDA で解決できます。

あなたがしなければならないことは次のとおりです。

• 入力がaあり、スタックが空であるかa、上部に がある場合、スタックをプッシュaします。pop b、bがトップの場合。

• 入力がbあり、スタックが空であるかb、上部に がある場合、スタックをプッシュbします。pop a、a上にある場合。

• 最後に、文字列が終了したらa、スタックの一番上にある場合は null 入力で最終状態に移動します。aそれ以外の場合は、 よりも多くのはありませんb。

Answer 2

>という形式a^nb^mの文字列を意味していると思います。nm

アイデアは比較的簡単aです。スタックに (ループで) プッシュしb、別のループに切り替えてaスタックからポップします。スタックが空になると、FAIL であきらめます。最初のループで または 以外のものが得られた場合a、bまたは 2 番目のループで 以外のものbが得られた場合、FAIL であきらめます。

最後に別のものをポップしようとしa、スタックが空の場合は FAIL であきらめます (つまり、スタックに少なくとも と同じ数b、aおそらくそれ以上の がありました)。そうでない場合は、成功です。

編集：補足として、これがこの質問に適したサイトであるとは確信していません。プログラマーの方が良いかもしれません。よくわからないので、投票しないでください。