決定論的プッシュダウンオートマトン

オートマトン理論において、決定性プッシュダウンオートマトン（DPDAまたはDPA ）はプッシュダウンオートマトンの一種である。決定性プッシュダウンオートマトンクラスは、文脈自由言語の適切なサブセットである決定性文脈自由言語を受け入れる。^[1]

マシンの遷移は、現在の状態と入力シンボル、およびスタックの現在の最上位シンボルに基づきます。スタックの下位のシンボルは表示されず、すぐには効果がありません。マシンのアクションには、スタックの最上位をプッシュ、ポップ、または置き換えることが含まれます。決定論的プッシュダウン オートマトンには、入力シンボル、状態、および最上位スタック シンボルの同じ組み合わせに対して、最大で 1 つの有効な遷移があります。これが、非決定論的プッシュダウン オートマトンとの違いです。

(必ずしも決定論的ではない) PDA は、 7 つのタプルとして定義できます。 ${\displaystyle M}$

${\displaystyle M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,Z_{0}\,,A\,,\delta \,)}$

どこ

• ${\displaystyle Q\,}$有限の状態集合である
• ${\displaystyle \Sigma \,}$入力シンボルの有限集合である
• ${\displaystyle \Gamma \,}$スタックシンボルの有限集合である
• ${\displaystyle q_{0}\,\in Q\,}$開始状態です
• ${\displaystyle Z_{0}\,\in \Gamma \,}$スタック開始シンボル
• ${\displaystyle A\,\subseteq Q\,}$、ここで、受理状態または最終状態の集合は${\displaystyle A}$
• ${\displaystyle \delta \,}$は遷移関数であり、

${\displaystyle \delta \colon (Q\,\times (\Sigma \,\cup \left\{\varepsilon \,\right\})\times \Gamma \,)\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})}$

ここで、 はクリーネ星であり、は「の要素のすべての有限文字列（空文字列を含む）の集合」であり、 は空文字列を表し、 は集合 の冪集合であることを意味します。${\displaystyle *}$${\displaystyle \Gamma^{*}}$ ${\displaystyle \epsilon }$${\displaystyle \ガンマ}$${\displaystyle \epsilon }$${\displaystyle {\mathcal {P}}(X)}$${\displaystyle X}$

M は、次の条件の両方を満たす場合、 決定論的です。

• 任意の に対して、集合には最大で 1 つの要素が含まれます。${\displaystyle q\in Q,a\in \Sigma \cup \left\{\varepsilon \right\},x\in \Gamma }$${\displaystyle \delta (q,a,x)\,}$
• 任意の に対して、 ならば、任意の${\displaystyle q\in Q,x\in \Gamma }$${\displaystyle \delta (q,\varepsilon ,x)\not =\emptyset \,}$${\displaystyle \delta \left(q,a,x\right)=\emptyset }$${\displaystyle a\in \Sigma .}$

受け入れ基準には、空のスタックによる受け入れと最終状態による受け入れの2つがあります。これら2つは、決定性プッシュダウンオートマトンでは同等ではありません（非決定性プッシュダウンオートマトンでは同等です）。空のスタックで受け入れられる言語は、最終状態で受け入れられ、接頭辞のない言語です。つまり、言語内のどの単語も、言語内の他の単語の接頭辞ではありません。^{[2] [3]}

通常の受け入れ基準は最終状態であり、この受け入れ基準は決定論的文脈自由言語を定義するために使用されます。

が PDA によって受け入れられる言語である場合、 に属するすべての文字列に対して初期構成から受け入れ計算まで単一の計算がある場合に限り、 は DPDA でも受け入れられます。が PDA によって受け入れられる場合、それは文脈自由言語であり、 が DPDA によって受け入れられる場合、それは決定論的文脈自由言語 (DCFL) です。 ${\displaystyle L(A)}$${\displaystyle A}$${\displaystyle L(A)}$${\displaystyle L(A)}$

すべての文脈自由言語が決定論的というわけではありません。このため、DPDA は PDA よりも厳密に弱いデバイスになります。たとえば、 0 と 1 のアルファベットの偶数長回文の言語L _{p は}、文脈自由文法 S → 0S0 | 1S1 | ε を持ちます。この言語の DPDA が存在し、文字列 0 ⁿが見つかると、その可能な継続0 ⁿ 11 0 ⁿ ∈ L _pと0 ⁿ 11 0 ^{n +2} ∉ L _pを区別できるように、スタックを使用して長さn を記憶する必要があります。したがって、0 ⁿ 11 0 ^{n を}読み取った後、「11」後の長さと「11」前の長さを比較すると、スタックは再び空になります。このため、文字列0 ⁿ 11 0 ⁿ 0 ⁿ 11 0 ⁿ ∈ L _pと0 ⁿ 11 0 ⁿ 0 ^{n +2} 11 0 ^{n +2} ∉ L _pは区別できない。^[4]

DPDAを単一の状態に制限すると、受け入れられる言語のクラスはLL(1)言語^[5]に限定され、これはDCFLの適切なサブクラスである^[6]。PDAの場合、この制限は受け入れられる言語のクラスに影響を与えない。

決定性文脈自由言語（最終状態によって決定性PDAに受け入れられる）の閉包特性は、文脈自由言語とは大きく異なります。例えば、それらは（事実上）補集合に対して閉じていますが、和集合に対しては閉じていません。決定性PDAによって受け入れられる言語の補集合が決定性PDAによっても受け入れられることを証明するのは、無限の計算を避け、入力シンボルを読み取らずにスタックを操作する遷移を正しく処理する必要があるため、難しいです。^[7]

補集合の結果として、決定論的 PDA が入力アルファベット上のすべての単語を受け入れるかどうかは、補集合が空かどうかをテストすることによって決定できます。これは文脈自由文法では不可能です (したがって、一般的な PDA では不可能です)。

ジェロー・セニゼルグ（1997）は、決定性PDAの同値問題（つまり、2つの決定性PDA AとBが与えられたとき、L(A)=L(B)であるか？）が決定可能であることを証明し、^{[8] [9] [10]その証明により、彼は2002年の}ゲーデル賞を受賞しました。非決定性PDAの場合、同値性は決定不可能です。

• ハンバーガー、ヘンリー、ダナ・S・リチャーズ(2002)。コンピュータサイエンスのための論理および言語モデル。アッパーサドルリバー、ニュージャージー州 07458: プレンティスホール。pp. 284–331。ISBN 0-13-065487-6。{{cite book}}: CS1 maint: location (link)