Sammanhangskänslig grammatik

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 januari 2016; kontroller kräver 10 redigeringar .

En kontextberoende grammatik ( KZ-grammatik , kontextgrammatik ) är ett specialfall av en formell grammatik (typ 1 enligt Chomsky-hierarkin ), där den vänstra och högra delen av alla produktioner kan omges av terminal och icke-terminal symboler.

Ett specialfall av formell grammatik är också sammanhangsfri grammatik .

Ett språk som kan specificeras av en CV-grammatik kallas ett sammanhangsberoende språk eller ett CV-språk.

Formell definition

En formell grammatik G=(N, T, I, P) är kontextkänslig om alla regler för P har formen: αAβ → αωβ

där A ∈ N (det vill säga en enda icke-terminal symbol), ω ∈ (N ∪ T) + (det vill säga en icke-tom sträng som består av terminala och/eller icke-terminala symboler), α, β ∈ ( N ∪ T)* (det vill säga vilken sträng som helst som består av terminala och/eller icke-terminala tecken).

Exempel

Följande grammatik anger ett sammanhangskänsligt språk : $\{a^{n}b^{n}c^{n}:n\geq 1\}$

$S\högerpil aSBC$
$S\högerpil aBC$
$CB\rightarrow CZ$
$CZ\rightarrow WZ$
$WZ\rightarrow WC$
$WC\rightarrow BC$
$aB\högerpil ab$
$bB\högerpil bb$
$bC\högerpil bc$
$cC\högerpil cc$

Så här ser generationskedjan aaa bbb ccc ut:

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}}

Se även

JFLAP plattformsoberoende automatsimulator, Turingmaskiner, grammatik, automatgrafritning

Litteratur

Cook D., Baze G. Kapitel 8. Språk och grammatik // Computer Mathematics = Computer Mathematics. - M . : Vetenskap. Fizmatlit, 1990. - 384 sid. — ISBN 5-02-014216-6 .

Formella språk och formella grammatiker
Allmänna begrepp	Chomsky hierarki Alfabet Ord
Typ 0	Obegränsad grammatik Turing maskin uppräknat språk Lösbart språk
Typ 1	Sammanhangskänslig grammatik Kontextkänsligt språk Linjärt begränsad automat
Typ 2	Kontextfri grammatik Tvetydig grammatik Kontextfritt språk Pushdown-automat ( deterministisk ) Tillväxt Lemma Ogdens Lemma Cooks teorem
Typ 3	Vanlig grammatik vanligt språk Vanligt uttryck Tillståndsmaskin ( deterministisk , icke- deterministisk ) DFA-minimering Bestämning av NFA Myhill-Nerodes sats
analysera	LL analysator LR-parser Rekursiv nedstigningsmetod Kok-Yngre-Kasami-algoritm