Spojovací gramatika - Conjunctive grammar

Spojovací gramatiky jsou třídou formálních gramatik studovaných v formální jazyk Teorie. Rozšiřují základní typ gramatiky, bezkontextové gramatiky,s spojení operace. Kromě explicitní spojky umožňují spojovací gramatiky implicitní disjunkce reprezentováno více pravidly pro jeden neterminální symbol, který je jediným logickým spojovacím výrazem vyjádřitelným v bezkontextových gramatikách. Konjunkci lze použít zejména k určení průniku jazyků. Další rozšíření spojovací gramatiky známé jako Booleovské gramatiky navíc umožňuje explicitní negace.

Pravidla spojovací gramatiky mají formu

${ displaystyle A až alpha _ {1} And ldots And alpha _ {m}}$

kde ${ displaystyle A}$ je neterminální a${ displaystyle alpha _ {1}}$, ..., ${ displaystyle alpha _ {m}}$jsou řetězce tvořené symboly v ${ displaystyle Sigma}$ a ${ displaystyle V}$ (konečné sady koncové a neterminální symboly Takové pravidlo neformálně tvrdí, že každý řetězec ${ displaystyle w}$ přes ${ displaystyle Sigma}$který splňuje každou ze syntaktických podmínek představovaných ${ displaystyle alpha _ {1}}$, ..., ${ displaystyle alpha _ {m}}$proto splňuje podmínku definovanou v ${ displaystyle A}$.

Formální definice

Spojovací gramatika ${ displaystyle G}$ je definovánan-tice ${ displaystyle G = (V, Sigma, R, S)}$ kde

1. PROTI je konečná množina; každý prvek ${ displaystyle v ve V}$ je nazýván neterminální symbol nebo a proměnná. Každá proměnná představuje jiný typ fráze nebo klauze ve větě. Proměnné se také někdy nazývají syntaktické kategorie.
2. Σ je konečná sada termináls, disjunktní od PROTI, které tvoří skutečný obsah věty. Sada terminálů je abeceda jazyka definovaného gramatikou G.
3. R je konečná sada inscenací, každá z těchto forem ${ displaystyle A rightarrow alpha _ {1} & ldots & alpha _ {m}}$ pro některé ${ displaystyle A}$ v ${ displaystyle V}$ a ${ displaystyle alpha _ {i} in (V cup Sigma) ^ {*}}$. Členové R se nazývají pravidlos nebo Výrobas gramatiky.
4. S je počáteční proměnná (nebo počáteční symbol), která se používá k reprezentaci celé věty (nebo programu). Musí to být prvek PROTI.

Je běžné vypsat všechny pravé strany pro stejnou levou stranu na stejném řádku pomocí | (dále jen symbol potrubí ) je oddělit. Pravidla ${ displaystyle A rightarrow alpha _ {1} & ldots & alpha _ {m}}$ a ${ displaystyle A rightarrow beta _ {1} & ldots & beta _ {n}}$ lze tedy psát jako ${ displaystyle A rightarrow alpha _ {1} & ldots & alpha _ {m} | beta _ {1} & ldots & beta _ {n}}$.

Existují dvě ekvivalentní formální definice jazyka specifikovaného spojovací gramatikou. Jedna definice je založena na reprezentaci gramatik systému jazykové rovnice s sjednocením, průnikem a zřetězením a vzhledem k jeho nejmenšímu řešení. Druhá definice zobecňujeChomsky generativní definice bezkontextových gramatik pomocí přepisování termínů přes spojku a zřetězení.

Definice odvozením

Pro všechny struny ${ displaystyle u, v in (V cup Sigma cup {{ text {"("}}, { text {"}} & { text {"}}, { text {" ) ”}} }) ^ {*}}$, říkáme u přímo výnosy proti, psáno jako ${ displaystyle u Rightarrow v ,}$, pokud

• buď existuje pravidlo ${ displaystyle A rightarrow alpha _ {1} & ldots & alpha _ {m} v R}$ takhle ${ displaystyle u , = u_ {1} Au_ {2}}$ a ${ displaystyle v , = u_ {1} ( alpha _ {1} & ldots & alpha _ {m}) u_ {2}}$,
• nebo existuje řetězec ${ displaystyle w in (V cup Sigma) ^ {*}}$ takhle ${ displaystyle u , = u_ {1} (w & ldots & w) u_ {2}}$ a ${ displaystyle v , = u_ {1} wu_ {2}}$.

Pro libovolný řetězec ${ displaystyle w in Sigma ^ {*},}$ říkáme G generuje w, psáno jako ${ displaystyle S { stackrel {*} { Rightarrow}} w}$, pokud ${ displaystyle existuje k geq 1 , existuje , u_ {1}, cdots, u_ {k} in (V cup Sigma cup {{ text {“(”}}, { text {„}} & { text {“}}, { text {„)“}} }) ^ {*}}$ takhle ${ displaystyle S = , u_ {1} Rightarrow u_ {2} Rightarrow cdots Rightarrow u_ {k} , = w}$.

Jazyk gramatiky ${ displaystyle G = (V, Sigma, R, S)}$ je sada všech řetězců, které generuje.

Příklad

Gramatika ${ displaystyle G = ( {S, A, B, C, D }, {a, b, c }, R, S)}$, s produkcemi

${ displaystyle S rightarrow AB & DC}$,

${ displaystyle A rightarrow aA | epsilon}$,

${ displaystyle B rightarrow bBc | epsilon}$,

${ displaystyle C rightarrow cC | epsilon}$,

${ displaystyle D rightarrow aDb | epsilon}$,

je spojovací. Typická derivace je

${ displaystyle S Rightarrow (AB & DC) Rightarrow (aAB & DC) Rightarrow (aB & DC) Rightarrow (abBc & DC) Rightarrow (abc & DC) Rightarrow (abc & aDbC) Rightarrow (abc) & abC) Rightarrow (abc & abcC) Rightarrow (abc & abc) Rightarrow abc}$

To lze ukázat ${ displaystyle L (G) = {a ^ {n} b ^ {n} c ^ {n}: n geq 0 }}$. Jazyk není kontextový, což dokazuje čerpání lemmatu pro bezkontextové jazyky.

Algoritmy analýzy

Ačkoli je expresivní síla konjunktivní gramatiky větší než u bezkontextových gramatik, konjunktivní gramatiky si zachovávají některé z nich. Nejdůležitější je, že existují zobecnění hlavních algoritmů pro analýzu bez kontextu, včetně lineárního času rekurzivní sestup kubický čas generalizovaný LR kubický čas Cocke-Kasami-mladší,stejně jako Valiant's algoritmus běží tak rychle jako násobení matic.

Teoretické vlastnosti

Vlastnost, která je již nerozhodnutelná pro bezkontextové jazyky nebo jejich konečné průniky, musí být nerozhodnutelná také pro spojovací gramatiky; tyto zahrnují: prázdnota, konečnost, pravidelnost, bezkontextovost,^{[n 1]} začlenění a rovnocennost.^{[č. 2]}

Rodina spojovacích jazyků je uzavřena spojením, průnikem, zřetězení a Kleene hvězda, ale ne pod řetězový homomorfismus, předpona, přípona a podřetězec. Uzavření pod doplňkem a pod homomorfismem řetězce bez ε jsou stále otevřené problémy (od roku 2001).^[1]:533

Byla prozkoumána expresivní síla gramatik nad jednopísmennou abecedou.^{[Citace je zapotřebí ]}

Tato práce poskytla základ pro studium jazykové rovnice obecnější formy.

Synchronizované automaty se střídavým posunem dolů

Aizikowitz a Kaminski^[2] představil novou třídu pushdown automaty (PDA) synchronizované střídavé pushdown automaty (SAPDA). Dokázali, že je ekvivalentní spojivkovým gramatikám, stejně jako nedeterministické PDA jsou ekvivalentní bezkontextovým gramatikám.

Poznámky

Reference

externí odkazy

• Artur Jeż (2007). "Spojovací gramatiky generují nepravidelné unární jazyky" (PDF) (Prezentace se konaly na Mezinárodní konference o vývoji v teorii jazyků ). Citováno 5. listopadu 2019.
• „Stránka Alexandra Okhotina o spojovacích gramatikách“. 9. října 2011. Citováno 5. listopadu 2019.
• Alexander Okhotin (2007). „Devět otevřených problémů pro konjunktivní a booleovské gramatiky“. Bulletin EATCS. Archivovány od originál dne 29. 9. 2007.
• Alexander Okhotin (2013). "Konjunktivní a booleovské gramatiky: Skutečný obecný případ bezkontextových gramatik". Recenze informatiky. 9: 27–59. doi:10.1016 / j.cosrev.2013.06.001. Tento příspěvek nahrazuje dřívější průzkumy, „Přehled spojovacích gramatik“ (Bulletin of EATCS, 2004) a „Devět otevřených problémů pro spojovací a booleovské gramatiky“
• Jeż, Artur (2008). "Spojovací gramatiky generují nepravidelné unární jazyky". International Journal of Foundations of Computer Science. 19 (3): 597–615. doi:10.1142 / S012905410800584X. Verze technické zprávy (pdf)^{[trvalý mrtvý odkaz ]}