Automata-theory-pushdown-automata-acceptance
提供：Dev Guides
プッシュダウンオートマトンの受け入れ
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}
例
*L = \ {0 ^ n ^ 1 ^ n ^ |を受け入れるPDAを構築します。 n≥0}*溶液
この言語は、L = \ {ε、01、0011、000111、……………………….. }
ここで、この例では、 'a' と 'b' の数は同じである必要があります。
- 最初に、空のスタックに特別なシンボル '$' を配置します。
- その後、状態* q〜2〜*で、入力0に遭遇し、topがNullの場合、0をスタックにプッシュします。 これは繰り返される場合があります。 入力1に遭遇し、topが0の場合、この0をポップします。
- その後、状態* q〜3〜*で、入力1に遭遇し、topが0の場合、この0をポップします。 これも繰り返されます。 入力1に遭遇し、topが0の場合、top要素をポップします。
- 特別なシンボル「$」がスタックの一番上で見つかると、ポップアウトされ、最終的に受け入れ状態q〜4〜になります。
例
L = \ {ww ^ R ^ |を受け入れるPDAを構築しますw =（a + b）*}
溶液
最初に、特別なシンボル「$」を空のスタックに入れます。 状態* q〜2〜では、 *w が読み取られています。 状態* q〜3〜では、入力に一致すると0または1がそれぞれポップされます。 他の入力が与えられると、PDAはデッド状態になります。 その特別な記号「$」に到達すると、受け入れ状態 q〜4〜*に移動します。
