Gramatyka koniunkcyjna

Gramatyki koniunkcyjne to klasa gramatyk formalnych studiowanych w teorii języka formalnego . Rozszerzają podstawowy typ gramatyk, gramatyk bezkontekstowych , o operację koniunkcji . Oprócz koniunkcji jawnej, gramatyki koniunkcyjne dopuszczają niejawną dysjunkcję reprezentowaną przez wiele reguł dla pojedynczego symbolu nieterminalnego, który jest jedynym łącznikiem logicznym możliwym do wyrażenia w gramatykach bezkontekstowych. Koniunkcji można użyć w szczególności do określenia przecięcia języków. Dalsze rozszerzenie gramatyk koniunkcyjnych, znanych jako gramatyki boolowskie, dodatkowo umożliwia wyraźną negację .

Reguły gramatyki koniunkcyjnej mają formę

${\ Displaystyle A \ do \ alfa _ {1} \ I \ ldots \ I \ alfa _ {m}}$

gdzie jest $nieterminalem$ i , ..., ${\ Displaystyle$$\ alpha _ {m}}$ są łańcuchami utworzonymi z symboli w $\ Sigma }$$Displaystyle A$$)$ ( odpowiednio skończone zbiory symboli terminalnych i nieterminalnych . Nieformalnie $spełnia$ reguła stwierdza, że ​​​​każdy ciąg $powyżej$$,$${\ displaystyle \ alpha _ {m}}$ warunków składniowych reprezentowanych przez ..., α spełnia zatem warunek określony przez ${\ displaystyle A}$ .

Definicja formalna

Gramatyka koniunkcyjna $jest$ zdefiniowana przez 4- krotkę gdzie $G = (V, \ Sigma, R, S)}$

1. V jest zbiorem skończonym; $zmienną$ element jest symbolem lub . _ Każda zmienna reprezentuje inny typ frazy lub klauzuli w zdaniu. Zmienne są czasami nazywane kategoriami syntaktycznymi.
2. Σ jest skończonym zbiorem końcówek s, rozłącznych z V , które składają się na rzeczywistą treść zdania. Zbiorem terminali jest alfabet języka określonego przez gramatykę G .
3. R to skończony zbiór produkcji, z których każda ma postać ${\ Displaystyle A \ rightarrow \ alpha _ {1} \&\ ldots \&\ alpha _ {m}}$ dla pewnego ${ m.} \ Displaystyle A}$ w ${\ Displaystyle V}$${\ Displaystyle \ alpha _ {i} \ in (V \ cup \ Sigma) ^ {*}}$ ja . Członkowie R nazywani są regułami lub wytworami gramatyki.
4. S jest zmienną początkową (lub symbolem początkowym), używaną do reprezentowania całego zdania (lub programu). Musi być elementem V.

Często wymienia się wszystkie prawe strony tej samej lewej strony w tej samej linii, używając | ( symbol rury ), aby je rozdzielić. Zasady ${\ Displaystyle A \ rightarrow \ alpha _ {1} \ & \ ldots \& \ alpha _ {m}}$ i ${\ Displaystyle A \ rightarrow \beta _{1}\&\ldots \&\beta _{n}}$ można zatem zapisać jako ${\ Displaystyle A \ rightarrow \ alpha _ {1} \& \ ldots \&\ alpha _ {m} \ |\ \ beta _ {1} \&\ ldots \&\ beta _ { n}}$ .

Istnieją dwie równoważne definicje formalne języka określonego przez gramatykę koniunkcyjną. Jedna definicja opiera się na przedstawieniu gramatyki jako układu równań językowych z sumą, przecięciem i konkatenacją oraz rozważeniu jej najmniejszego rozwiązania. Druga definicja uogólnia generatywną definicję gramatyk bezkontekstowych Chomsky'ego , używając przepisywania terminów nad koniunkcją i konkatenacją.

Definicja przez pochodzenie

Dla dowolnych ciągów ${\ Displaystyle u, v \ in (V \ kubek \ Sigma \ kubek \ {{\ tekst {„ (”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}} , mówimy, że u bezpośrednio$ daje v , zapisane jako ${\ Displaystyle u \ Strzałka w prawo v \}$ , jeśli

• albo istnieje reguła taka, że ${\ Displaystyle A \ rightarrow \ alpha _ {1} \ & \ ldots \&\ alpha _ {m} \ in R}$${\ Displaystyle u \ = u_ {1} Au_ {2}}$ i ${\ Displaystyle v \ = u_ {1} (\ alfa _ {1}\&\ldots \&\alpha _{m})u_{2}}$ ,
• $_ \ = u_ {1} (w \ & \ ldots \& w) u_ {2}}$ istnieje $,$ taki i ${\ Displaystyle v \, = u_ {1} wu_ {2}}$ .

${\ Displaystyle w \ in \ Sigma ^ {*},}$ ∈ mówimy, że generuje w , zapisywane jako ${\ Displaystyle S \ {\ stackrel {*} {\ Rightarrow}} \ w}$ , jeśli ${\ Displaystyle \ istnieje k \ geq 1 \, \ istnieje \,u_{1},\cdots,u_{k}\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{ ”}} {\ tekst {“)”}} \}) ^ {*}}$ takie, że ${\ Displaystyle S = \, u_ {1} \ Rightarrow u_{2}\Strzałka w prawo \cdots \Strzałka w prawo u_{k}\,=w}$ .

Językiem $_$ _

Przykład

sol $\ Displaystyle G = (\ {S, A, B, C, D \} \ {a,b,c\},R,S)}$ , z produkcjami

$\ Displaystyle S \ rightarrow AB \ & DC}$ ,

${\ Displaystyle A \ rightarrow aA \ |\ \ epsilon}$ ,

${\ Displaystyle B \ rightarrow bBc \ |\ \ epsilon}$ ,

${\ Displaystyle C \ strzałka w prawo cC \ |\ \ epsilon}$ ,

${\ Displaystyle D \ rightarrow aDb \ |\ \ epsilon}$ ,

jest spójny. Typowe wyprowadzenie to

${\ Displaystyle S \ Rightarrow (AB \ &DC)\Strzałka w prawo (aAB\&DC)\Strzałka w prawo (aB\&DC)\Strzałka w prawo (abBc\&DC)\Strzałka w prawo (abc\&DC)\Strzałka w prawo (abc\&aDbC)\Strzałka w prawo (abc\&abC)\Strzałka w prawo (abc\&abcC )\Strzałka w prawo (abc\&abc)\Strzałka w prawo abc}$

${\ Displaystyle L (G) = \ {a ^ {n} b ^ {n} c ^ {n}: n \$ za . Język nie jest bezkontekstowy, czego dowodzi lemat o pompowaniu dla języków bezkontekstowych .

Algorytmy parsowania

Chociaż siła wyrazu gramatyk koniunkcyjnych jest większa niż gramatyk bezkontekstowych, gramatyki koniunkcyjne zachowują niektóre z tych ostatnich. Co najważniejsze, istnieją uogólnienia głównych bezkontekstowych algorytmów analizowania, w tym rekurencyjne zejście w czasie liniowym, uogólniony LR w czasie sześciennym , algorytm Cocke-Kasami-Younger w czasie sześciennym , a także algorytm Valianta działający tak szybko jak macierz mnożenie.

Właściwości teoretyczne

Właściwość, która jest nierozstrzygalna już dla języków bezkontekstowych lub ich skończonych przecięć, musi być nierozstrzygalna także dla gramatyk koniunkcyjnych; należą do nich: pustka , skończoność , regularność , bezkontekstowość , inkluzja i równoważność.

Rodzina języków koniunkcyjnych jest zamknięta na zjednoczenie, przecięcie, konkatenację i gwiazdę Kleene'a , ale nie na homomorfizm ciągów , przedrostek , sufiks i podłańcuch. Zamknięcie pod dopełnieniem i pod homomorfizmem strun wolnych od ε są nadal problemami otwartymi (od 2001 r.).

Zbadano siłę wyrazu gramatyk nad jednoliterowym alfabetem.

Ta praca dała podstawę do badania równań językowych o bardziej ogólnej formie.

Zsynchronizowane naprzemienne automaty dociskowe

Aizikowitz i Kaminski wprowadzili nową klasę automatów przesuwających w dół (PDA) zwanych zsynchronizowanymi automatami przesuwającymi w dół (SAPDA). Udowodnili, że jest to równoważne gramatyce koniunkcyjnej w taki sam sposób, jak niedeterministyczne PDA są równoważne gramatyce bezkontekstowej.

Linki zewnętrzne

• Artura Jeża (2007). „Gramatyka koniunkcyjna generuje nieregularne języki jednoargumentowe” (PDF) (slajdy wykładu wygłoszone na Międzynarodowej Konferencji na temat Rozwoju Teorii Języka ) . Źródło 5 listopada 2019 r .
• „Strona Aleksandra Okhotina poświęcona gramatyce koniunkcyjnej” . 9 października 2011 . Źródło 5 listopada 2019 r .
• Aleksander Okhotin (2007). „Dziewięć otwartych problemów dla gramatyk koniunkcyjnych i boolowskich” . Biuletyn EATCS . Zarchiwizowane od oryginału w dniu 2007-09-29.
• Aleksander Okhotin (2013). „Gramatyka koniunkcyjna i boolowska: prawdziwy ogólny przypadek gramatyk bezkontekstowych”. Przegląd informatyki . 9 : 27–59. doi : 10.1016/j.cosrev.2013.06.001 . Ten artykuł zastępuje wcześniejsze badania, „Przegląd gramatyk koniunkcyjnych” (Biuletyn EATCS, 2004) i „Dziewięć otwartych problemów dla gramatyk koniunkcyjnych i boolowskich”
• Jeż, Artur (2008). „Gramatyka koniunkcyjna generuje nieregularne języki jednoargumentowe”. Międzynarodowy Dziennik Podstaw Informatyki . 19 (3): 597–615. doi : 10.1142/S012905410800584X . Wersja raportu technicznego (pdf)