埋め込みプッシュダウンオートマトン

埋め込みプッシュダウンオートマトンまたはEPDA は、木結合文法(TAG)によって生成された言語を解析するための計算モデルです。文脈自由文法解析プッシュダウンオートマトンに似ていますが、シンボルを格納するために単純なスタックを使用する代わりに、シンボルを格納する反復スタックのスタックがあり、TAG に文脈自由文法と文脈依存文法、または軽度の文脈依存文法のサブセットの間の生成能力を与えます。埋め込みプッシュダウンオートマトンを、 より計算能力の高いネストされたスタックオートマトンと混同しないでください。 ^{[引用が必要]}

EPDAは、K. Vijay-Shankerが1988年の博士論文で初めて記述しました。^{[1]それ以来、EPDAは軽度文脈依存文法のクラスのより完全な記述に適用され、}チョムスキー階層の改良に重要な役割を果たしてきました。これにより、線形インデックス文法などのさまざまな部分文法を定義できます。^[2]

自然言語は伝統的に文脈自由文法（変形生成文法と計算言語学を参照）を用いて分析されてきたが、このモデルはオランダ語のような依存関係が交差する言語にはうまく機能しない。このような状況ではEPDAが適している。詳細な言語分析はJoshi, Schabes（1997）に記載されている。^[3]

EPDA は、埋め込みスタック を介してアクセスできるスタックのセットを備えた有限状態マシンです。各スタックにはスタック アルファベット の要素が含まれているため、スタックの要素を で定義します。ここで、星印はアルファベットの クリーネ閉包です。${\displaystyle \,\Gamma }$${\displaystyle \,\sigma _{i}\in \Gamma ^{*}}$

各スタックはその要素によって定義できるため、オートマトンの 番目のスタックを二重ダガー記号、^{[明確化が必要]}で表します。ここで はスタック内の次にアクセス可能な記号です。したがって、スタックの埋め込みスタックは で表すことができます。^{[明確化が必要]}${\displaystyle \,j}$${\displaystyle \,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{ j,1}\}}$${\displaystyle \,\sigma _{j,k}}$${\displaystyle \,m}$${\displaystyle \,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}}$

EPDAは7組で定義される。

${\displaystyle \,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})}$どこ

• ${\displaystyle \,Q}$状態の有限集合である。
• ${\displaystyle \,\Sigma }$入力アルファベットの有限集合です。
• ${\displaystyle \,\Gamma }$有限スタックアルファベットです。
• ${\displaystyle \,q_{0}\in Q}$開始状態です。
• ${\displaystyle \,Q_{\textrm {F}}\subseteq Q}$最終状態の集合です。
• ${\displaystyle \,\sigma _{0}\in \Gamma }$スタックの初期シンボル
• ${\displaystyle \,\delta :Q\times \Sigma \times \Gamma \rightarrow S}$は遷移関数であり、 はの有限部分集合です。${\displaystyle \,S}$${\displaystyle \,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}}$

したがって、遷移関数は、状態、入力文字列の次のシンボル、および現在のスタックの最上位シンボルを受け取り、次の状態、埋め込みスタックにプッシュおよびポップされるスタック、現在のスタックのプッシュとポップ、および次の遷移で現在のスタックと見なされるスタックを生成します。より概念的には、埋め込みスタックがプッシュおよびポップされ、現在のスタックがオプションで埋め込みスタックにプッシュバックされ、必要な他のスタックがその上にプッシュされ、最後のスタックが次の反復で読み取られるスタックになります。したがって、スタックは現在のスタックの上と下の両方にプッシュできます。

特定の構成は次のように定義されます。

${\displaystyle \,C(M)=\{q,\Upsilon _{m}\ldots \Upsilon _{1},x_{1},x_{2}\}\in Q\times (\ddagger \Gamma ^{+})^{*}\times \Sigma ^{*}\times \Sigma ^{*}}$

ここで、 は現在の状態、 は埋め込みスタック内のスタックで、 は現在のスタック、 は入力文字列の場合、はマシンによってすでに処理された文字列の部分、 は処理される部分で、その先頭は現在読み取られたシンボル です。空文字列は暗黙的に終了シンボルとして定義されることに注意してください。空文字列が読み取られたときにマシンが最終状態にある場合は、入力文字列全体が受け入れられ、そうでない場合は拒否されます。このような受け入れられた文字列は、言語の要素です 。${\displaystyle \,q}$${\displaystyle \,\Upsilon }$${\displaystyle \,\Upsilon _{m}}$${\displaystyle \,x=x_{1}x_{2}\in \Sigma ^{*}}$${\displaystyle \,x_{1}}$${\displaystyle \,x_{2}}$${\displaystyle \,\epsilon \in \Sigma }$

${\displaystyle \,L(M)=\left\{x|\{q_{0},\Upsilon _{0},\epsilon ,x\}\rightarrow _{M}^{*}\{q_{\textrm {F}},\Upsilon _{m}\ldots \Upsilon _{1},x,\epsilon \}\right\}}$

ここで、およびは文字列を解析するために必要な回数だけ適用される遷移関数を定義します。 ${\displaystyle \,q_{\textrm {F}}\in Q_{\textrm {F}}}$${\displaystyle \,\rightarrow _{M}^{*}}$

EPDAの非公式な説明は、Joshi, Schabes (1997)、^[3] Sect.7、p. 23-25にも記載されています。

軽度文脈依存クラスに対応する、より正確に定義された言語の階層は、David J. Weirによって定義されました。^[4] Nabil A. Khabbazの研究に基づいて、^{[5] [6] Weirの制御言語階層は}、言語クラスの可算セットの 包含階層です^{[明確化]。}レベル1は文脈自由として定義され、レベル2は木結合と他の3つの文法のクラスです。

階層内の レベルk言語の特性の一部を次に示します。

• レベルk言語はレベル( k  + 1)言語クラスに適切に含まれる。
• レベルk言語は時間内に解析できる${\displaystyle O(n^{3\cdot 2^{k-1}})}$
• レベルkには言語が含まれていますが、${\displaystyle \{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}}$${\displaystyle \{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}}$
• レベルkには言語が含まれていますが、${\displaystyle \{w^{2^{k-1}}|w\in \{a,b\}^{*}\}}$${\displaystyle \{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}}$

 これらの特性は、Joshi によって課された軽度文脈依存言語の条件によく対応しており (少なくともk > 1 が小さい場合)、 kが大きくなるにつれて、言語クラスは、ある意味では軽度文脈依存ではなくなります。

• 組み合わせ範疇文法

• ローラ・カルメイヤー (2010)。文脈自由文法を超えた構文解析。Springer Science & Business Media。ISBN 978-3-642-14846-0。