プッシュダウンオートマトンの受け入れ

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

最初に、特別なシンボル「$」を空のスタックに入れます。状態でq2w読んでいます。状態でq3、入力と一致すると、各0または1がポップされます。他の入力が与えられると、PDAはデッド状態になります。その特別な記号「$」に到達すると、受け入れ状態になりますq4