Tilanneherkkä kielioppi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. tammikuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta .

Kontekstiriippuvainen kielioppi ( KZ-grammar , kontekstikielioppi ) on formaalisen kieliopin ( Chomsky-hierarkian tyyppi 1 ) erikoistapaus, jossa kaikkien tuotantojen vasen ja oikea osa voi olla terminaalisen ja ei-terminaalisen ympärillä. symboleja.

Formaalin kieliopin erikoistapaus on myös yhteydetön kielioppi .

Kieli , joka voidaan määrittää CV-kieliopilla, kutsutaan kontekstiriippuvaksi kieleksi tai CV-kieleksi.

Muodollinen määritelmä

Formaali kielioppi G=(N, T, I, P) on kontekstiherkkä, jos kaikki P:n säännöt ovat muotoa: αAβ → αωβ

missä A ∈ N (eli yksittäinen ei-päätemerkki), ω ∈ (N ∪ T) + (eli ei-tyhjä merkkijono, joka koostuu pääte- ja/tai ei-päätteisistä symboleista), α, β ∈ ( N ∪ T)* (eli mikä tahansa merkkijono, joka koostuu pääte- ja/tai ei-päätemerkeistä).

Esimerkkejä

Seuraava kielioppi määrittää kontekstiherkän kielen : $\{a^{n}b^{n}c^{n}:n\geq 1\}$

$S\rightarrow aSBC$
$S\rightarrow aBC$
$CB\rightarrow CZ$
$CZ\rightarrow WZ$
$WZ\rightarrow WC$
$WC\rightarrow BC$
$aB\rightarrow ab$
$bB\nuoli oikealle bb$
$bC\rightarrow bc$
$cC\rightarrow cc$

Tältä aaa bbb ccc sukupolviketju näyttää:

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

Katso myös

JFLAP cross-platform automaattinen simulaattori, Turingin koneet, kielioppi, automaatiograafin piirtäminen

Kirjallisuus

Cook D., Baze G. Luku 8. Kielet ja kieliopit // Computer Mathematics = Computer Mathematics. - M . : Tiede. Fizmatlit, 1990. - 384 s. — ISBN 5-02-014216-6 .

Muodolliset kielet ja viralliset kieliopit
Yleiset käsitteet	Chomsky-hierarkia Aakkoset Sana
Tyyppi 0	Rajoittamaton kielioppi Turingin kone lueteltu kieli Ratkaiseva kieli
Tyyppi 1	Tilanneherkkä kielioppi Tilannekohtainen kieli Lineaarisesti rajattu automaatti
Tyyppi 2	Kontekstiton kielioppi Epäselvä kielioppi Kontekstiton kieli Työntöautomaatti ( deterministinen ) Kasvu Lemma Ogdenin Lemma Cookin lause
Tyyppi 3	Tavallinen kielioppi tavallinen kieli Tavallinen ilme Tilakone ( deterministinen , ei - deterministinen ) DFA-minimointi NFA:n määrittäminen Myhill-Neroden lause
jäsentäminen	LL analysaattori LR jäsentäjä Rekursiivinen laskeutumismenetelmä Kok-Younger-Kasami-algoritmi