問題タブ [pushdown-automaton]

{0 ⁱ 1 ^j 2 ^k | 0 <= i <= j <= k }

この言語用の PDA を設計することは可能ですか?

答えはノーだと思います。少なくとも文脈自由文法を使用してのみ定義できます。

しかし、その理由はわかりません。これについては、議論と説明が必要です。

最近、最初に見つけてフォローするという問題に直面しました

ここで、 A のプロダクションに左再帰があるため、どちらが正しい {a} 、 {empty,a} の最初の A と混同されています。A の最初に空の文字列を含めるかどうか混乱しています。--------------編集済み---------------

これの最初と次は何でしょう ,,これは私が今まで見た中でとても紛らわしい文法です

解析テーブルを使用して、この文法が LL(1) にないことを証明する必要がありますが、1 つのセルに 2 つのエントリを取得できなかったため、証明できませんでした。

だから私は、プッシュダウン オートマトンと文脈自由言語に関するテストの勉強をしていて、この 1 つの構造に固執しています。

以下で説明する 1 つの部分を除いて、このオートマトンのすべての部分が完全に機能しています。

認識する必要がある言語は次のとおりです。{ x#y#z#w | x, y, z, w in {0, 1}+ with x ≠ w and y ≠ z }.

したがって、私が抱えている問題は、Xi と Wi を比較することです。これは、オートマトンが W を処理する時点では Wi の要素がわからないためです。これは、私が設計した方法です。

X の内容を格納すると、各要素をポップオフして W の要素と比較するときに、逆の順序でポップオフするため、000111 と 111000 が同じ文字列であると見なされ、PDA は拒否する必要がありますが拒否されます。明確に受け入れます (それらは異なる文字列です)。これは一例にすぎません。これにより、他の入力が正しく分析されなくなります。

X の内容を逆の順序でスタックにプッシュする方法があれば、それらは元の形式でポップオフされるため、文字列の内容を正しく比較できます。

普通にプッシュした後にスタックの内容を逆にする方法があれば、これも解決策にたどり着くことができます。

どんな助けでも大歓迎です。ありがとう。

a^2n b^n, n>0 を受け入れる pda プッシュダウン オートマトンを作成しようとしていますが、最後の部分が正しいかどうかはわかりません

http://wiki.apidesign.org/wiki/Impossible

私はこれを見ましたが、なぜこの問題が不可能に見えるのかわかりません。「マシン」に与えられた文字列は常に有限ですよね？

したがって、10 億のゼロと 10 億の 1 があるとしても、その文字列に対して true または false を返すスクリプトを簡単に作成できます (これは true/accept になります)。

別の入力が「00011」である可能性があり、無効になります。

私はおそらくここで何かを理解していませんでしたが、この問題は私には「コード化可能」に思えます。

次の問題に近づくのに問題があります。

次の言語の文脈自由文法を教えてください.

この質問にアプローチする最良の方法は何ですか? 現時点では、直感を使ってこのような質問を解決していますが、役立つテクニックはありますか? つまり、この言語の PDA がどのようになるかを考えて、そこから文法を導出できますか? 文法 A と B を使用して文法 G = A と B を見つける方法はありますか?

これを解決する方法を見つけるのに苦労しているので、どんな助けでも大歓迎です。

ありがとう。