プッシュダウンオートマトン

有限オートマトンに記憶装置としてスタックを加えたオートマトン($\varepsilon$ 遷移をもつ非決定性有限オートマトン($\varepsilon$-NFA))をプッシュダウンオートマトン(PDA;Pushdown Automaton)といいます.

PDAの状態遷移関数

状態 $p \in Q$ ,入力 $\alpha \in \Sigma$ ,スタックの一番上に積まれている記号を $A \in \Gamma$ とします.
このとき,次の状態 $q \in Q$ と,次にスタックに積む(書きこむ)記号列 $\alpha \in \Gamma^{*}$ を定める関数をプッシュダウンオートマトン(PDA)の状態遷移関数といい,以下のように表します.\[\delta(p,a,A) = (q,\alpha)\]

PDAの定義

4つの集合 $Q,\Sigma,\Gamma,F$ を,

としたとき,初期状態 $q_{0} \in Q$,初期スタック記号 $Z_{0} \in \Gamma$ からプッシュダウンオートマトン $M$ は以下のように定義されます.\[M=(Q,\Sigma,\Gamma,\delta,q_{0},Z_{0},F)\]

Vita brevis, ars longa. Omnia vincit Amor.





















C*環 スタック 連接 conjunction 正規表現 regular expression 非決定性有限オートマトン NFA 状態遷移関数