Gramatică sensibilă la context

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 6 ianuarie 2016; verificările necesită 10 modificări .

O gramatică dependentă de context ( KZ-gramatică , gramatică de context ) este un caz special de gramatică formală (tip 1 conform ierarhiei Chomsky ), în care părțile din stânga și din dreapta ale tuturor producțiilor pot fi înconjurate de terminale și non-terminale. simboluri.

Un caz special de gramatică formală este și gramatica fără context .

O limbă care poate fi specificată de o gramatică CV este numită limbă dependentă de context sau limbaj CV.

Definiție formală

O gramatică formală G=(N, T, I, P) este sensibilă la context dacă toate regulile lui P sunt de forma: αAβ → αωβ

unde A ∈ N (adică un singur simbol non-terminal), ω ∈ (N ∪ T) + (adică un șir nevid format din simboluri terminale și/sau non-terminale), α, β ∈ ( N ∪ T)* (adică orice șir format din caractere terminale și/sau non-terminale).

Exemple

Următoarea gramatică specifică o limbă sensibilă la context : $\{a^{n}b^{n}c^{n}:n\geq 1\}$

$S\săgeata spre dreapta aSBC$
$S\săgeata dreapta aBC$
$CB\rightarrow CZ$
$CZ\rightarrow WZ$
$WZ\rightarrow WC$
$WC\rightarrow BC$
$aB\rightarrow ab$
$bB\rightarrow bb$
$bC\rightarrow bc$
$cC\rightarrow cc$

Așa arată lanțul de generație 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}}

Vezi și

Simulator de automată multiplatformă JFLAP , mașini Turing, gramatică, desen grafic automat

Literatură

Cook D., Baze G. Capitolul 8. Limbi și gramatici // Computer Mathematics = Computer Mathematics. - M .: Știință. Fizmatlit, 1990. - 384 p. — ISBN 5-02-014216-6 .

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tip 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami