プッシュダウンオートマトンの受け入れ
PDAの受容性を定義する方法は2つあります。
最終状態の許容性
最終状態の受け入れ可能性では、PDAは、文字列全体を読み取った後、PDAが最終状態にあるときに文字列を受け入れます。開始状態から、任意のスタック値で最終状態になる移動を行うことができます。最終的な状態になる限り、スタック値は関係ありません。
PDA（Q、∑、S、δ、q 0、I、F）の場合、最終状態のセットFで受け入れられる言語は-です。
L（PDA）= {w | （q 0、w、I）⊢*（q、ε、x）、q∈F}
任意の入力スタック文字列 x。
空のスタックの許容性
ここで、PDAは、文字列全体を読み取った後、PDAがスタックを空にしたときに、文字列を受け入れます。
PDA（Q、∑、S、δ、q 0、I、F）の場合、空のスタックで受け入れられる言語は-です。
L（PDA）= {w | （q 0、w、I）⊢*（q、ε、ε）、q∈Q}
例
受け入れるPDAを構築する L = {0n 1n | n ≥ 0}
解決
この言語は、L = {ε、01、0011、000111、.............................}を受け入れます。
ここで、この例では、 ‘a’ そして ‘b’ 同じである必要があります。
最初に特別なシンボルを置きます ‘$’ 空のスタックに。
その後、状態で q2、入力0に遭遇し、topがNullの場合、0をスタックにプッシュします。これは繰り返される可能性があります。そして、入力1に遭遇し、topが0の場合、この0をポップします。
その後、状態で q3、入力1に遭遇し、topが0の場合、この0をポップします。これも反復する可能性があります。そして、入力1に遭遇し、topが0の場合、top要素をポップします。
特殊記号「$」は、スタックの最上部に遭遇した場合、それが飛び出していると、それは最終的に受理状態qに行く4。
例
L = {ww R |を受け入れるPDAを構築します。w =（a + b）*}
Solution
最初に、特別なシンボル「$」を空のスタックに入れます。状態でq2、 w読んでいます。状態でq3、入力と一致すると、各0または1がポップされます。他の入力が与えられると、PDAはデッド状態になります。その特別な記号「$」に到達すると、受け入れ状態になりますq4。