Processing math: 0%

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

有限オートマトンに記憶装置としてスタックを加えたオートマトン（$\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$：状態の集合
• $\Sigma$：入力記号の集合
• $\Gamma$：スタック記号の集合
• $\delta$：状態遷移関数
• $F$：受理状態集合

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

Mathematics is the language with which God has written the universe.