Loading article…
オートマトン理論では、ネストされたスタックオートマトン とは、追加のスタックになり得るデータを含むスタックを利用できる有限オートマトンです。 [1]スタックオートマトンと同様に、ネストされたスタックオートマトンもスタック内を上下に移動して、現在のシンボルを読み取ることができます。さらに、任意の場所で新しいスタックを作成し、そのスタックを操作し、最終的にそのスタックを破棄して、古いスタックで操作を続行することができます。このように、スタックは任意の深さまで再帰的にネストできますが、オートマトンは常に最も内側のスタックのみで動作します。
ネストされたスタックオートマトンにはインデックス言語を認識する能力があり、[2]実際、インデックス言語のクラスは一方向非決定性ネストされたスタックオートマトンが受け入れる言語のクラスとまったく同じです。[1] [3]
ネストされたスタックオートマトンを、計算能力が低い埋め込みプッシュダウンオートマトンと混同しないでください。 [引用が必要]
正式な定義
オートマトン
（非決定性双方向）ネストスタックオートマトンとは、タプル⟨ Q ,Σ,Γ,δ, q 0 , Z 0 , F ,[,], ] ⟩であり、
- Q、Σ、Γはそれぞれ状態、入力シンボル、スタックシンボルの空でない有限集合である。
- [, ], ]は Σ ∪ Γ に含まれない異なる特殊記号である。
- [ は入力文字列と（サブ）スタック文字列の両方の左端マーカーとして使用されます。
- ]はこれらの文字列の右端のマーカーとして使用されます。
- ]はスタック全体を表す文字列の最後の終了マーカーとして使用されます。[注 1]
- 拡張入力アルファベットはΣ' = Σ ∪ {[,]}で定義され、拡張スタックアルファベットはΓ' = Γ ∪ {]}で定義され、入力移動方向のセットはD = {-1,0,+1}で定義されます。
- δは有限制御であり、Q × Σ' × (Γ' ∪ [Γ' ∪ { ] , [ ] })からQ × D × ([Γ * ∪ D )の有限部分集合への写像であり、δは[注2]
- 非公式には、（サブ）スタックの一番上のシンボルとその前の左端マーカー「[」は1つのシンボルとして扱われる。[4] δは次のように表される。
- 現在の状態、
- 現在の入力シンボル、および
- 現在のスタックシンボル、
- および出力
- 次の州、
- 入力を移動する方向、および
- スタック上で移動する方向、またはスタックの最上位シンボルを置き換えるシンボルの文字列。
- q 0 ∈ Q は初期状態であり、
- Z 0 ∈ Γ は初期スタックシンボルであり、
- F ⊆ Q は最終状態の集合です。
構成
このようなオートマトンの構成、つまり瞬間的な記述は、3つの要素 ⟨ q 、[ a 1 a 2 ... a i ... a n -1 ]、 [ Z 1 X 2 ... X j ... X m -1 ] ⟩で構成され、ここ で
- q ∈ Qは現在の状態であり、
- [ a 1 a 2 ... a i ... a n -1 ] は入力文字列です。便宜上、a 0 = [ およびa n = ] が定義されています[注 3]入力内の現在の位置、つまり0 ≤ i ≤ nのi は、それぞれの記号に下線が引かれて示されます。
- [ Z 1 X 2 ... X j ... X m -1 ]はサブスタックを含むスタックです。便宜上、X 1 = [ Z 1 [注4]およびX m = ]が定義されています。スタック内の現在の位置、つまり1 ≤ j ≤ mのjは、それぞれの記号に下線を付けて示されます。
例
実行例（入力文字列は表示されません）:
プロパティ
オートマトンが入力を再読み込みできる場合（「双方向オートマトン」）、ネストされたスタックは、プレーンスタックと比較して、追加の言語認識機能をもたらしません。[5]
ギルマンとシャピロは、ネストされたスタックオートマトンを使用して、特定のグループの単語問題を解きました。[6]
注記
- ^ Ahoはもともと「[」、「]」、「]」の代わりにそれぞれ「$」、「¢」、「#」を使用していました。Aho (1969)、p.385上部を参照。
- ^ 並置は文字列（集合）の連結を表し、集合の和集合∪よりも結合優先度が高くなります。たとえば、[Γ'は"["で始まりΓ'の記号で終わる長さ2の文字列すべての集合を表します。
- ^ Aho はもともと、左と右のスタック マーカー、つまり $ と ¢ を、それぞれ右と左の入力マーカーとして使用していました。
- ^ (サブ)スタックの最上位のシンボルとその前の左エンドマーカー「[」は、1 つのシンボルとして表示されます。
参考文献
- ^ ab Aho, Alfred V. (1969年7月). 「ネストスタックオートマトン」. Journal of the ACM . 16 (3): 383–406. doi : 10.1145/321526.321529 . S2CID 685569.
- ^ パルティー、バーバラ、アリス・ター・ミューレン、ロバート・E・ウォール（1990）。言語学における数学的手法。クルーワー・アカデミック・パブリッシャーズ。pp.536–542。ISBN 978-90-277-2245-4。
- ^ John E. Hopcroft、Jeffrey D. Ullman (1979)。オートマトン理論、言語、計算入門。Addison- Wesley。ISBN 0-201-02988-X。こちら:p.390
- ^ アホ（1969）、p.385上
- ^ Beeri, C. (1975年6月). 「双方向ネストスタックオートマトンと双方向スタックオートマトンは同等である」. Journal of Computer and System Sciences . 10 (3): 317–339. doi : 10.1016/s0022-0000(75)80004-3 .
- ^ Shapiro, Robert Gilman Michael (1998 年 12 月 4 日).ネストされたスタックオートマトンによって単語問題が解かれるグループについて(技術レポート). arXiv : math/9812028 . CiteSeerX 10.1.1.236.2029 . S2CID 12716492.