だから私は、プッシュダウン オートマトンと文脈自由言語に関するテストの勉強をしていて、この 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 の内容を逆の順序でスタックにプッシュする方法があれば、それらは元の形式でポップオフされるため、文字列の内容を正しく比較できます。
普通にプッシュした後にスタックの内容を逆にする方法があれば、これも解決策にたどり着くことができます。
どんな助けでも大歓迎です。ありがとう。