Visibly Pushdown Automaton - Jack of All Trades, Master of None

nested wordをアクセプトするオートマトンをnested wordオートマトンという。VPAはnested wordオートマトンと等価な普通の(nested wordでない)語を受理するオートマトン。

nested wordオートマトンと関係がありそうだなあ…位のことは、遷移関数の定義を見ると、(直感的には)直ぐわかる。その辺りの対応に関する証明の詳細は調べてない。

普通、VPAと言った場合は決定的なものを指すっぽい(未確認)

VPAは6つ組 $(Q,\hat{\Sigma},\Gamma,\delta,q_0,F)$ の形で定義されれる。

ここで、

$Q$ は状態の有限集合
$\hat{\Sigma}$ は入力アルファベットを表す。 $\hat{\Sigma}$ は $\Sigma_c,\Sigma_r,\Sigma_{int}$ の3つの部分からなり、それぞれcall記号,ret記号,内部記号を含む.
$\Gamma$ はスタックアルファベットと呼ばれる有限集合で、空のスタックを表す特別な記号 $\bot\in\Gamma$ を含む.
は遷移関数.ここで
- $\delta_c : Q\times\Sigma_c\rightarrow Q\times\Gamma$ (call遷移関数)
- $\delta_r : Q\times\Sigma_r\times\Gamma\rightarrow Q$ (ret遷移関数)
- $\delta_{int} : Q\times\Sigma_{int}\rightarrow Q$ (内部遷移関数)
$q_0\in Q$ は初期状態
$F\subseteq Q$ は受理状態の集合