Vestavěný pushdown automat - Embedded pushdown automaton

An vestavěný pushdown automat nebo EPDA je výpočetní model pro analýzu jazyků generovaných stromové gramatiky (ZNAČKY). Je to podobné jako u bezkontextová gramatika -parsování zasunovací automat, ale namísto použití roviny zásobník k ukládání symbolů má hromadu iterovaných hromádek, které ukládají symboly, což dává TAG generativní kapacitu mezi bezkontextovými a kontextové gramatiky nebo podmnožina mírně kontextové gramatiky Zabudované automaty pushdown by neměly být zaměňovány s vnořené automaty zásobníku které mají větší výpočetní sílu.^{[Citace je zapotřebí ]}

Historie a aplikace

EPDA poprvé popsal K. Vijay-Shanker ve své disertační práci z roku 1988.^[1] Od té doby byly použity k úplnějším popisům tříd gramatik mírně citlivých na kontext a měly důležité role při zdokonalování Chomského hierarchie. Různé subgrammars, jako je lineární indexovaná gramatika, lze tedy definovat.^[2] EPDA také začínají hrát důležitou roli při zpracování přirozeného jazyka.

Zatímco přirozené jazyky byly tradičně analyzovány pomocí bezkontextových gramatik (viz transformačně-generativní gramatika a výpočetní lingvistika ), tento model nefunguje dobře pro jazyky se zkříženými závislostmi, jako je nizozemština, situace, pro které se EPDA dobře hodí. Podrobná lingvistická analýza je k dispozici v Joshi, Schabes (1997).^[3]

Teorie

EPDA je konečný stavový stroj se sadou hromádek, ke kterým lze sami přistupovat prostřednictvím vložený zásobník. Každý zásobník obsahuje prvky zásobník abeceda ${ displaystyle , gama}$, a tak definujeme prvek zásobníku pomocí ${ displaystyle , sigma _ {i} v Gamma ^ {*}}$, kde je hvězda Kleene uzavření abecedy.

Každý zásobník lze potom definovat z hlediska jeho prvků, proto označujeme ${ displaystyle , j}$th stack v automatu pomocí symbolu dvojité dýky: ${ displaystyle , Upsilon _ {j} = ddagger sigma _ {j} = { sigma _ {j, k}, sigma _ {j, k-1}, ldots, sigma _ { j, 1} }}$,^{[je zapotřebí objasnění ]} kde ${ displaystyle , sigma _ {j, k}}$ bude dalším přístupným symbolem v zásobníku. The vložený zásobník z ${ displaystyle , m}$ stohy lze tedy označit ${ displaystyle , { Upsilon _ {j} } = { ddagger sigma _ {m}, ddagger sigma _ {m-1}, ldots, ddagger sigma _ {1} } in ( ddagger Gamma ^ {+}) ^ {*}}$.^{[je zapotřebí objasnění ]}

Definujeme EPDA septuplem (7 n-tic)

${ displaystyle , M = (Q, Sigma, Gamma, delta, q_ {0}, Q _ { textrm {F}}, sigma _ {0})}$ kde

• ${ displaystyle , Q}$ je konečná sada státy;
• ${ displaystyle , Sigma}$ je konečná množina vstupní abeceda;
• ${ displaystyle , gama}$ je konečný zásobník abeceda;
• ${ displaystyle , q_ {0} v Q}$ je počáteční stav;
• ${ displaystyle , Q _ { textrm {F}} subseteq Q}$ je sada konečné stavy;
• ${ displaystyle , sigma _ {0} v Gamma}$ je symbol počátečního zásobníku
• ${ displaystyle , delta: Q times Sigma times Gamma rightarrow S}$ je přechodová funkce, kde ${ displaystyle , S}$ jsou konečné podmnožiny ${ displaystyle , Q krát ( ddagger Gamma ^ {+}) ^ {*} krát Gamma ^ {*} krát ( ddagger Gamma ^ {+}) ^ {*}}$.

Přechodová funkce tedy přebírá stav, další symbol vstupního řetězce a horní symbol aktuálního zásobníku a generuje další stav, přičemž hromádky, které mají být tlačeny a vysunuty na vložený zásobník, tlačení a vyskakování aktuálního zásobníku a hromádky, které mají být považovány za aktuální hromádky v příštím přechodu. Koncepčnější je vložený zásobník je tlačen a vysunut, aktuální zásobník je volitelně zasunut zpět na vložený zásobník, a jakékoli další hromádky, které by někdo chtěl, jsou tlačeny nad to, přičemž poslední hromádka je ta, ze které se čte v další iteraci. Stohy lze tedy tlačit nad i pod aktuální zásobník.

Daná konfigurace je definována

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

kde ${ displaystyle , q}$ je aktuální stav, ${ displaystyle , Upsilon}$s jsou hromádky v vložený zásobník, s ${ displaystyle , Upsilon _ {m}}$ aktuální zásobník a pro vstupní řetězec ${ displaystyle , x = x_ {1} x_ {2} v Sigma ^ {*}}$, ${ displaystyle , x_ {1}}$ je část řetězce již zpracovaná strojem a ${ displaystyle , x_ {2}}$ je část, která má být zpracována, přičemž její hlava je aktuálním načteným symbolem. Všimněte si, že prázdný řetězec ${ displaystyle , epsilon in Sigma}$ je implicitně definován jako zakončovací symbol, kde je-li stroj při čtení prázdného řetězce v konečném stavu, celý vstupní řetězec je přijato, a pokud ne, je zamítnuto. Takový přijato řetězce jsou prvky jazyka

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

kde ${ displaystyle , q _ { textrm {F}} v Q _ { textrm {F}}}$ a ${ displaystyle , rightarrow _ {M} ^ {*}}$ definuje přechodovou funkci použitou tolikrát, kolikrát je potřeba k analýze řetězce.

Neformální popis EPDA lze nalézt také v Joshi, Schabes (1997),^[3] Oddíl 7, s. 23-25.

k- objednejte si EPDA a Weirovu hierarchii

Tato část může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Specifický problém je: potřebuje přepsat na základě Kallmeyer str. 199 Prosím pomozte vylepšit tuto sekci jestli můžeš. (Srpna 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Přesněji definovanou hierarchii jazyků, které odpovídají třídě mírně citlivé na kontext, definoval David J. Weir.^[4]Na základě práce Nabil A. Khabbaz,^[5][6]Weirova jazyková hierarchie je omezení hierarchie spočetné sady jazykových tříd^{[vyjasnit ]} Kde Úroveň 1 je definován jako bezkontextový a Úroveň 2 je třída sousedních stromů a další tři gramatiky.

Následuje několik vlastností Level-k jazyky v hierarchii:

• Úroveň-k jazyky jsou správně obsaženy v úrovni - (k + 1) jazyková třída
• Úroveň-k jazyky lze analyzovat ${ displaystyle O (n ^ {3 cdot 2 ^ {k-1}})}$ čas
• Úroveň-k obsahuje jazyk ${ displaystyle {a_ {1} ^ {n} dotso a_ {2 ^ {k}} ^ {n} | n geq 0 }}$, ale ne ${ displaystyle {a_ {1} ^ {n} dotso a_ {2 ^ {k + 1}} ^ {n} | n geq 0 }}$
• Úroveň-k obsahuje jazyk ${ displaystyle {w ^ {2 ^ {k-1}} | w in {a, b } ^ {*} }}$, ale ne ${ displaystyle {w ^ {2 ^ {k-1} +1} | w in {a, b } ^ {*} }}$

Tyto vlastnosti dobře odpovídají (alespoň pro malé k > 1) na podmínky mírně kontextově citlivých jazyků uložené Joshi a podobně k se zvětší, jazyková třída bude v jistém smyslu méně citlivá na kontext.

Viz také

• kombinační kategoriální gramatika

Reference

Další čtení

• Laura Kallmeyer (2010). Analýza nad rámec bezkontextových gramatik. Springer Science & Business Media. ISBN  978-3-642-14846-0.