pushdown-automaton - プッシュダウンオートマトン

Question

0 ^ m 1^nのpdaをどのように記述しますか。ここで|m| > = | n |; 0の数が1の数以上ですか？

私は考えていました：

• 1または0が表示された場合は、スタックにプッシュします
• 別の0または0の束が表示された場合は、それをスタックにプッシュします
• 1が表示された場合は、スタックにプッシュします
• その後に別の1が表示された場合は、スタックからポップします。

しかし、私はこれが正しいとは思いません。誰か助けてもらえますか？

Answer 1

0と1の数が等しい場合を考えてみましょう。

簡単に始めましょう。1から始めることも、0から始めることもできます。これにより、2つの異なる言語の和集合が得られます。0の数は1の数よりも大きく、その逆も同様です。

したがって、空の文字列も有効です（これにより、最初の状態が最終状態になるという手がかりが得られます）。

次に、最終的には同じ数の0と1が上下する可能性があることを確認します。

文字列について考えてみましょう。

010101または101010。常に空のスタックに戻ることに気づきました。これは扱いやすいです。

基本的に、開始開始が受け入れ状態でもあるPDAがあります。

表記を知っているかどうかわからないので、平易な英語で保管しています。

q0、q1、q2の3つの状態があります。

q0は、最終および初期の開始状態です。

q0-> q1には1つの遷移1、e-> $があります（1を読み取り、空のスタックの$記号を押します）。

q1には、0、1-> eおよび1、e、1の自己ループがあります（0を読み取る場合は、1をポップします）、（1を読み取る場合は、1を押します）。

開始状態q0に戻るもう1つの遷移があります。

q1-> q0 0、$-> e（0を読み取り、スタックは空になります）この時点で0と1の数は同じです。

代わりに0をプッシュしてポップすることを除いて、状態q2に対してこれを行います。したがって、すべてが1と0の正反対です。

そうすれば、非決定論的に0をいくつでも持つことができます。これは、あなたに任せます。ヒント：これを処理するために、どこかに1つの自己ループを作成できます。これは、実際には、0から1の数と同じかそれ以上の数を取得するために追加する必要がある状態があと1つだけです。

=====================

したがって、平易な英語では、最初に1または0から始める2つのケースを考慮する必要があります。次に、スタックが再び空になった場合は、初期/最終状態に戻って、再び1または0になるかどうかを確認します。

例：

10010011

最初に1を読んでください。次に、0を読み取るので、今度は次の文字列で最初からやり直すようなものです。

010011

今回は0を読み取り、1を読み取り、最初からやり直します。

0011

0を読み取り、0を読み取り、0をプッシュし、1を読み取り、0をポップし、別の1を読み取り（スタックは空になります）、初期/最終状態に戻ります。

お役に立てば幸いです。

Answer 2

私が割り当てを正しく理解しているなら、あなたはこの方法を複雑にしているのです。0 ^ m 1 ^ nは、0の束の後に1の束が続くことを意味しますが、1を見た後、0の合法的な文字列はありません。最初にスタックに記号を付けて、いつ空になるかを確認します（通常は＃）。その後、基本的に0を数える必要があり（スタックにプッシュします）、1が表示されたら、スタックからポップします。入力が終了したら、スタックに0があるかどうか、または最初にスタックに配置した記号があるかどうかを確認します。