Nested stack automaton とは

オートマトン理論では、ネストされたスタックオートマトンは、追加のスタックとなることができるデータを含むスタックを利用できる有限オートマトンである。スタックオートマトンのように、ネストされたスタックオートマトンはスタック内で上下に動いて現在のシンボルを読み取ることができます。さらに、新しいスタックを作成し、そのスタックを操作し、最終的にスタックを破壊し、古いスタックで操作を続けることができます。このようにして、スタックは任意の深度に再帰的にネストできます。しかし、オートマトンは常に最も内側のスタックでのみ動作します。
ネストされたスタックオートマトンは、索引付けされた言語を認識することができ、実際には索引付き言語のクラスは、一方向の非決定的なネストされたスタックオートマトンによって受け入れられる言語のクラスです。
ネストされたスタックオートマトンは、計算能力が低い埋め込みプッシュダウンオートマトンと混同しないでください。