Automata-theory-pushdown-automata-introduction
プッシュダウンオートマトンの概要
PDAの基本構造
プッシュダウンオートマトンは、通常の文法用にDFAを設計するのと同様の方法で、コンテキストなしの文法を実装する方法です。 DFAは有限量の情報を記憶できますが、PDAは無限量の情報を記憶できます。
基本的にプッシュダウンオートマトンは-
「有限状態マシン」+「スタック」
プッシュダウンオートマトンには3つのコンポーネントがあります-
- 入力テープ、
- コントロールユニット
- 無限のサイズのスタック。
スタックヘッドは、スタックの一番上のシンボルをスキャンします。
スタックは2つの操作を行います-
- プッシュ-上部に新しいシンボルが追加されます。
- ポップ-一番上のシンボルが読み取られて削除されます。
PDAは入力シンボルを読み取る場合と読み取らない場合がありますが、すべての遷移でスタックの先頭を読み取る必要があります。
PDAは正式には7タプル（Q、∑、S、δ、q〜0〜、I、F）として記述できます-
- Q は有限状態数
- ∑ は入力アルファベットです
- S はスタックシンボルです
- *δ*は遷移関数です：Q×（∑∪\ {ε}）×S×Q×S *
- * q〜0〜*は初期状態です（q〜0〜∈Q）
- I は初期スタックトップシンボル（I∈S）
- F は受理状態の集合です（F∈Q）
次の図は、状態q〜1〜から状態q〜2〜へのPDAの遷移を示しており、a、b→c-とラベル付けされています-
これは、状態* q〜1〜で、入力文字列 *'a' に遭遇し、スタックのトップシンボルが 'b' の場合、 'b' をポップし、 'c' をプッシュすることを意味します。スタックの一番上で、状態* q〜2〜*に移動します。
PDAに関連する用語
瞬時の説明
PDAの瞬間的な記述（ID）は、トリプレット（q、w、s）で表されます。
- q は状態です
- w は消費されていない入力です
- s はスタックの内容です
ターンスタイル表記
「ターンスタイル」表記は、PDAの1つまたは複数の動きを表すIDのペアを接続するために使用されます。 移行のプロセスは、ターンスタイルシンボル「⊢」で示されます。
PDA（Q、∑、S、δ、q〜0〜、I、F）を考えます。 遷移は、次のターンスタイル表記法で数学的に表すことができます-
これは、状態 p から状態 q への遷移中に、入力シンボル 'a' が消費され、スタックの上部 'T' が新しい文字列 'α’に置き換えられることを意味します。 。
注-PDAのゼロ以上の移動が必要な場合は、記号（⊢*）を使用する必要があります。
