Kasvulemma kontekstittomille kielille

Kontekstivapaiden kielten kasvulemma on lemma, joka analogisesti säännöllisten kielten samannimisen lemman kanssa tekee suhteellisen helpoksi todistaa, että tietty kieli ei ole yhteydetön .

Sanamuoto

Jos L on CS-kieli aakkosten V yli, niin . Toisin sanoen mikä tahansa riittävän pitkä ketju CS-kielessä voidaan jakaa viiteen osaan niin, että toisen ja neljännen osan toistaminen mielivaltaisesti monta kertaa (ehkä 0) ei johda kielen ylittämiseen.
$(\olemassa n\in \mathbb{N})(\forall \alpha \in L: |\alpha|>n)(\olemassa u,x,v,y,w\in V^*):$
$\alpha =uxvyw\land |xy|>0\land |xvy|\leq n\land (\forall i\geq 0:ux^{i}vy^{i}w\in L).$

Todiste

Olkoon CS-kieli (V, N, S, G) annettu ja kielen kielioppi pelkistyy (eli se ei sisällä muotoa A → ε tai A → B olevia sääntöjä).

Koska ei-terminaalisten symbolien määrä on äärellinen, samoin kuin kunkin päättelysäännön pituus, ketjun pituus, jonka johdantopuun korkeus ei ylitä |N|, on myös ylhäältä rajoitettu tietyllä määrällä. numero n.

Ajatellaanpa ketjua . Yllä olevan johdosta sen johtopuun korkeus ylittää |N|, eli aksioomasta yhteen päätesymboleista tulee polku, jonka pituus on suurempi kuin ei-päätemerkkien lukumäärä. kieliopin symboleja. Koska jokaisessa vaiheessa korvataan yksi ei-päätemerkki, ainakin yksi ei-pääteinen Q-symboli korvataan kahdesti tällä polulla. Tästä seuraa, että on olemassa ketju xQy, jossa on ei-tyhjä x tai y, joka on johdettu Q:sta. Siksi johtamisprosessissa S →* α johtamisprosessi Q →* xQy voidaan toistaa niin monta kertaa kuin halutaan tai jättää pois. $\alpha: |\alpha|>n$

Triviaali seuraus: missä tahansa äärettömässä CS-kielessä on ääretön osajoukko merkkijonoja, joiden pituudet muodostavat kasvavan aritmeettisen progression.

Käyttöesimerkkejä

Kieli ei ole CS-kieli: on mahdotonta valita kahta ketjua ja ladata niitä poistumatta kielestä (sinun on ladattava kolme ketjua samanaikaisesti). $a^nb^nc^n, n \geq 0$
Kieli ei myöskään ole CS-kieli, mutta tätä ei voida enää todistaa "pumppaamalla": voit pumpata merkkejä a ja b "vyöhykkeitä" hyödyntäen sitä tosiasiaa, että c-merkkejä voi olla vähemmän. ketjussa. Mutta jos otamme huomioon kieleen kuuluvan merkkijonon, joko pumpattujen merkkijonojen poissulkeminen vie meidät pois kielestä, mikä on ristiriidassa pumppauslemman kanssa. $a^nb^nc^k, n,k \geq 0, k \leq n$ $a^nb^nc^n$
Kieli ei myöskään ole CF-kieli, koska se on ristiriidassa lemman seurauksen kanssa. $a^{n^2}$

Katso myös

Kirjallisuus

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
A.I. Belousov, S.B. Tkachev. Diskreetti matematiikka / toim. d.t.s. prof. V.S. Zarubina, Ph.D. prof. A. P. Krishchenko. - 4. painos, rev. — (matematiikka teknillisessä yliopistossa). - 2000 kappaletta. — ISBN 5-708-2886-4.

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