問題タブ [pushdown-automaton]

私は実際にそれを持っているとかなり確信していますが、それは42の構築ルールを持っており、うまく一般化されていません。より少ない構築ルールでそれを行うにはどうすればよいですか？

言語は{a、b} *で、aの数はbの数の5倍です。

言語{a^n（連結）b ^ m; m=5n}それはただ

S = aSbbbbb | λ

しかし、キャラクターが任意の順序になっていると、私は迷子になります。

有限オートマトンより強力で、決定論的プッシュ ダウン オートマトンより強力でないものはありますか?

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

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

私は完全に立ち往生しているポンピングレンマの質問があります...

L = {w ∈ {a, b, c}∗ : na (w) < nb (w) < nc (w)}

それはCFLですか？

これらの条件をすべて記憶するには、1 つのスタックだけでは十分ではないため、CFL ではないと考えています。na (w) < nb (w) または na (w)< nc (w),nb (w) < nc (w) であることを思い出すことができますが、na (w) < nb (w) < nc (w) ではありません。さらに、言語が a^pb^2pc^3p の場合と、|vy| の場合よりも p 回 L は CF ではありませんが、p 回ポンプアップすることは可能ですか?

または解決策のアイデアはありますか？

有限オートマトン、プッシュダウンオートマトン、チューリングマシンのタスクの例（手動で手動で解決するため）の優れたソースを探しています。

探していたのですが、特別なものは何も見つからなかったので、誰かが良い例を持っているのではないかと思います。前もって感謝します。

文脈自由文法を与える

{ w | wは{a、b、c、d} *の要素であり、aの数+bの数=cの数+Dの数}

この質問にどのようにアプローチしますか...？

文脈自由言語L={0 ^ n0 ^ n、n>=0}があるとしましょう。

PDAの場合：Μ= {A、Q、H、δ、q0、h0、F}次のようになります。

それが私の解決策ですが、問題があります。オートマトンは、00、ε、0000などの文字列を受け入れる必要があり、0、000は受け入れない必要があります。通常、0の数が偶数の文字列を受け入れます。

2つの例を試してみましょう。

最後の文字列は受け入れられません。文字列を認識する前にポップ数をチェックして、受け入れるかどうかを選択する方法がわかりません。誰かが私をトリガーするためのアイデア、手がかりはありますか？

かっことかっこが完全にネストされた文法の CFG と PDA を作成する必要があります。

これが正しいかどうか、またはそれから PDA を作成する方法がわかりませんか?

たとえば、バランスの取れた括弧と角かっこ（[] []）を受け入れるPDAを設計するにはどうすればよいでしょうか。始めるのに苦労しています。この問題の遷移関数を書くのに助けが必要です。どんな助けでも大歓迎です

私は理論の課題に取り組んでいますが、この質問は本当に考えさせられました。質問は次のとおりです。プッシュダウンオートマトンがキューオートマトンによってシミュレートできることを示してください。さて、最初はこれは簡単だと思っていましたが、L = {WW^R | W = {a, b}*} (W^R は W の逆) これはプッシュダウン オートマトンの一般的な形式で作成するのは簡単ですが、一般的な形式でそれを行う方法は思い浮かびません。キュー オートマトン。このために設計できる（有限の）一般的なケースはないと思います。シミュレートの意味を誤解しているだけかもしれないので、私もそれを考えすぎているかもしれません。とにかく、私は質問よりも間違っている可能性が高いですが、私が言及したケースではどのように機能しますか?

ご協力いただきありがとうございます。