PDAで受け入れられる言語

Question

私は、アイテムを押して、スタックの項目を押したり押したりするときに、プッシュダウンオートマトンの表記を理解するのに苦労しています。

文字列を受け入れるには、スタックが空である必要があることを理解します。ここで

は私のPDAです：

私は入力0011を言うための遷移図を作成する場合、私はこのようにそれを行うだろう：入力が空のスタックであるので

State   Input   Stack 

q0    0011   ɛ 

q0    011   0 

q0    11   00 

q0    1    100 

q0    ɛ    1100 

空ではない、これは受け入れられない？

もし私がうまくいくような入力をすれば...私はそれが間違っていると確信しています。なぜなら、私はPDAに任意の文字列を入れれば受け入れられないからです。

実際の質問をまとめると、最初の非終端記号（0、ɛ/ 0）（1、ɛ\ 1）の表記です。入力1の場合は、反対にする）？

2番目の端末では意味がありません...これは私を混乱させます（スタックや入力から文字列を取りますか？）スタックからアイテムを削除する必要があると思いますか？

これは、このPDAで使用できる言語が空のセットであることを意味しますか？もし私がどこに間違っているのか説明できないのですか？

Answer 1

は異なる慣習があるが、一つの共通の規則では、ときに受け入れることです：

1. 入力が使い果たされます。および
2. あなたは受理状態です。
3. スタックが空です。

実際にこれらのルールのいくつかのサブセットを使用し、他のルールセットを使用して、コンテキストフリー言語でも動作するシステムを取得できます。機械はこれらのシステムでは異なる解釈を持つだろうが、表現力は同じであろう。

上記の3点システムを想定すると、Welbogは指摘するように、このPDAはアルファベット{0, 1}を超える偶数長のパリドロームの言語を受け入れます。それぞれの国が何をしているのか話しましょう。

1. q0何度も繰り返し限り、あなたが望むように、0または1のいずれかを読み取り、それぞれ、0または1をプッシュし、スタックに。文字列xを読み取る場合は、文字列xをスタックにプッシュします。

2. q10または1のいずれかを読み取り、あなたがスタックの一番上にそのシンボルを持っている場合は、限り、あなたが望むようオーバーとゲインの上に、それをオフにポップ。文字列xを読むと、x^Rがスタックからポップします。

我々はq1受理状態を作り、そして入力がなくなったとき、スタックが空であることを要求した場合、それは意味：

1. xが読まれた場合我々は、x^Rからポップ状態q1でしばらく。
2. 状態q0にと書かれている場合、スタックにはx^Rが含まれています。
3. 我々はx^Rを読み、その後xと認められたので、我々は唯一のx^R xのような文字列を受け入れ、すなわち偶数長回文
4. また、任意の偶数長の回文があるため、それが受け入れられて、その結果、このPDAを通るパスを持っていますPDAは、入力シンボルの|x|/2の場合はq0のままで、q1に移行し、残りの|x|/2を読み取ることができます。 PDAは非決定論的なので、文字列が受け入れられると言うには十分です。