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 .
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.
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.
Triviaali seuraus: missä tahansa äärettömässä CS-kielessä on ääretön osajoukko merkkijonoja, joiden pituudet muodostavat kasvavan aritmeettisen progression.
Muodolliset kielet ja viralliset kieliopit | |
---|---|
Yleiset käsitteet | |
Tyyppi 0 | |
Tyyppi 1 |
|
Tyyppi 2 | |
Tyyppi 3 |
|
jäsentäminen |