Kontekstfølsom grammatik

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. januar 2016; checks kræver 10 redigeringer .

En kontekstafhængig grammatik ( KZ-grammatik , kontekstgrammatik ) er et specialtilfælde af en formel grammatik (type 1 ifølge Chomsky-hierarkiet ), hvor venstre og højre del af alle produktioner kan være omgivet af terminal og ikke-terminal symboler.

Et særligt tilfælde af formel grammatik er også kontekstfri grammatik .

Et sprog , der kan specificeres af en CV-grammatik, kaldes et kontekstafhængigt sprog eller et CV-sprog.

Formel definition

En formel grammatik G=(N, T, I, P) er kontekstafhængig, hvis alle reglerne i P har formen: αAβ → αωβ

hvor A ∈ N (det vil sige et enkelt ikke-terminalt symbol), ω ∈ (N ∪ T) + (det vil sige en ikke-tom streng bestående af terminale og/eller ikke-terminale symboler), α, β ∈ ( N ∪ T)* (dvs. enhver streng bestående af terminale og/eller ikke-terminale tegn).

Eksempler

Følgende grammatik specificerer et kontekstfølsomt sprog : $\{a^{n}b^{n}c^{n}:n\geq 1\}$

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

Sådan ser aaa bbb ccc generationskæden ud:

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 også

JFLAP cross-platform automat simulator, Turing maskiner, grammatik, automat graftegning

Litteratur

Cook D., Baze G. Kapitel 8. Sprog og grammatik // Computermatematik = Computermatematik. - M . : Videnskab. Fizmatlit, 1990. - 384 s. — ISBN 5-02-014216-6 .

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme