プッシュダウンオートマトン

Question

0^m 1^nのpdaを書くにはどうすればよいですか？ > = | n |; 0の数は1の数以上ですか？

私が考えていた：あなたが1または0を参照してください場合は、別の0または0の束を見た場合、スタックにそれをプッシュし、スタック

にそれをプッシュし、

• あなたが1を見れば
• は、あなたはその後、別の1を参照すると、スタック
• にそれをプッシュし、スタック

のオフにそれをポップしかし、私はこれが正しいとは思いません。誰か助けてもらえますか？

Answer 1

私が割り当てを正しく理解していれば、この方法を複雑にしています。 0^m 1^nは1の束が続く0の束を意味しますが、1を見た後には0を持つ正当な文字列はありません。まず、スタック上に記号を置いて、空であることを知ります＃）。その後、基本的に0をカウントする必要があります（スタックにプッシュしてください）。そして、1を見ると、スタックからポップします。入力が終了すると、最初にスタックに置かれた0またはシンボルがスタックにあるかどうかをチェックします。

Answer 2

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

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

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

次に、最終的に0と1の数が同じになることがわかります。

は、文字列を考えてみましょう：

010101または101010.あなたはそれが常に戻って空のスタックに行くに気づきました。これは簡単に処理できます。

基本的には、スタートの開始も受け入れ可能なPDAがあります。

私はあなたが表記法を知っているか分からないので、私は単純な英語でそれを保ちます。

あなたは3つの状態、q0、q1、q2を持っています。

q0は最終的かつ初期の開始状態です。

q0 - > q1は1遷移1、e - > $（1を読み、空のスタックの$記号をプッシュします）。

q1は0,1 - > eと1、e、1（0を読んだ場合は1を読み、1を読んだ場合は1をプッシュ）の自己ループを持ちます。

さらに1つの遷移が開始状態q0に戻ります。

q1 - > q0 0、$ - > e（読んだ場合は0、スタックは空になります）この時点で、0と1の合計が等しくなります。

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

それでは、非確定的に0をいくつでも持つことができます。私はこれをあなたに任せます。ヒント：これを処理するために、どこかに1つの自己ループを作成することができます。それは実際には、0と1の数よりも大きい数を得るために追加する必要がある州を1つだけ追加します

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

英語では最初に1か0で始まる2つのケースを考慮する必要があります。その後、空のスタックで再び終わると、最初/最後の状態に戻り、再び1または0があるかどうかを確認します。

例：

第1を読みます。

0にこの時間を読んで、1を読んで、とすべてやり直す：

0011次に、あなたがすべて最初からやり直すように、それはですので、文字列でこの時間は、0を読みます

0を読み、0を読み、1を読み、0を読み込み、別の1（スタックが空になっています）を読み込み、初期状態/最終状態に戻ります。

希望に役立ちます。