Kontextově citlivá gramatika

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. ledna 2016; kontroly vyžadují 10 úprav .

Kontextově závislá gramatika ( KZ-grammar , kontextová gramatika ) je speciální případ formální gramatiky (typ 1 podle Chomského hierarchie ), ve které mohou být levá a pravá část všech produkcí obklopena koncovými a neterminálními symboly.

Speciálním případem formální gramatiky je také bezkontextová gramatika .

Jazyk , který může být specifikován gramatikou CV, se nazývá kontextově závislý jazyk nebo jazyk CV.

Formální definice

Formální gramatika G=(N, T, I, P) je kontextově citlivá, pokud všechna pravidla P mají tvar: αAβ → αωβ

kde A ∈ N (tj. jeden nekoncový symbol), ω ∈ (N ∪ T) + (tj. neprázdný řetězec sestávající z koncových a/nebo nekoncových symbolů), α, β ∈ ( N ∪ T)* (to znamená jakýkoli řetězec skládající se z koncových a/nebo nekoncových znaků).

Příklady

Následující gramatika určuje kontextově citlivý jazyk : $\{a^{n}b^{n}c^{n}:n\geq 1\}$

$S\šipka doprava aSBC$
$S\šipka doprava aBC$
$CB\rightarrow CZ$
$CZ\rightarrow WZ$
$WZ\rightarrow WC$
$WC\rightarrow BC$
$aB\šipka doprava ab$
$bB\rightarrow bb$
$bC\šipka doprava bc$
$cC\rightarrow cc$

Takto vypadá generační řetězec aaa bbb ccc:

S

\Rightarrow _{1}aSBC

\Rightarrow _{1}a{\boldsymbol {aSBC}}BC

\Rightarrow _{2}aa{\boldsymbol {aBC}}BCBC

\Rightarrow _{3}aaaB{\boldsymbol {CZ}}CBC

\Rightarrow _{4}aaaB{\boldsymbol {WZ}}CBC

\Rightarrow _{5}aaaB{\boldsymbol {WC}}CBC

\Rightarrow _{6}aaaB{\boldsymbol {BC}}CBC

\Rightarrow _{3}aaaBBC{\boldsymbol {CZ}}C

\Rightarrow _{4}aaaBBC{\boldsymbol {WZ}}C

\Rightarrow _{5}aaaBBC{\boldsymbol {WC}}C

\Rightarrow _{6}aaaBBC{\boldsymbol {BC}}C

\Rightarrow _{3}aaaBB{\boldsymbol {CZ}}CC

\Rightarrow _{4}aaaBB{\boldsymbol {WZ}}CC

\Rightarrow _{5}aaaBB{\boldsymbol {WC}}CC

\Rightarrow _{6}aaaBB{\boldsymbol {BC}}CC

\Rightarrow _{7}aa{\boldsymbol {ab}}BBCCC

\Rightarrow _{8}aaa{\boldsymbol {bb}}BCCC

\Rightarrow _{8}aaab{\boldsymbol {bb}}CCC

\Rightarrow _{9}aaabb{\boldsymbol {bc}}CC

\Rightarrow _{10}aaabbb{\boldsymbol {cc}}C

\Rightarrow _{10}aaabbbc{\boldsymbol {cc}}

Viz také

Simulátor multiplatformního automatu JFLAP , Turingovy stroje, gramatika, kreslení grafů automatů

Literatura

Cook D., Baze G. Kapitola 8. Jazyky a gramatiky // Počítačová matematika = Počítačová matematika. - M .: Věda. Fizmatlit, 1990. - 384 s. — ISBN 5-02-014216-6 .

Formální jazyky a formální gramatiky
Obecné pojmy	Chomského hierarchie Abeceda Slovo
Typ 0	Neomezená gramatika Turingův stroj výčtový jazyk Řešitelný jazyk
Typ 1	Kontextově citlivá gramatika Kontextový jazyk Lineárně ohraničený automat
Typ 2	Bezkontextová gramatika Nejednoznačná gramatika Bezkontextový jazyk Zásobníkový automat ( deterministický ) Růstové lemma Ogdenovo lemma Cookova věta
Typ 3	Pravidelná gramatika regulární jazyk Regulární výraz Stavový stroj ( deterministický , nedeterministický ) Minimalizace DFA Stanovení NFA Myhillova-Nerodova věta
rozebrat	LL analyzátor LR analyzátor Metoda rekurzivního sestupu Kok-Younger-Kasami algoritmus