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

How would I write a pda for 0^m 1^n, where |m| >= |n|; the
number of 0’s is greater than or equal to the number of 1’s?

私は考えていた:

  • 1または0が表示されている場合は、スタックにスタックします
  • 別の0または複数の0がある場合は、スタックにスタックします
  • 1が表示されている場合は、スタックにスタックします
  • それ以降に1が表示された場合は、それをスタックからポップします。

しかし、私はこれが正しいとは思わない。誰か助けてもらえますか?

ベストアンサー

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

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

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

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

文字列を考えてみましょう:

010101または101010。あなたはそれがいつも空のスタックに戻ることに気付きました。これは簡単に処理できます。

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

私はあなたが表記法を知っているかどうか分からないので、私はちょうど英語のままにしておきます。

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

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

q0 -> q1 has 1 transition 1, e -> $ (read a 1, push a $
symbol for the empty stack).

q1 has a self loop of 0, 1 -> e and 1,e,1 (if you read a 0,
pop a 1), (if you read a 1, push a 1).

開始状態q0にもう一度遷移する。

q1 -> q0 0, $ -> e (read a 0, the stack is now empty) We
have equal number of 0s to 1s at this point.

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

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

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

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

例:

10010011

最初に1を読んでください。それから、0を読んだので、今度は文字列を使って何度もやり直すようです:

010011

今回は0を読んで、1を読んで、すべてを次のように開始します。

0011

0を読み、0を読み、0を読み、1を読んで、0をポップし、別の1(スタックが空になっています)を読み、初期状態/最終状態に戻ります。

希望が役立ちます。

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です