Növekedési lemma kontextusmentes nyelvekhez

A környezetfüggetlen nyelvek növekedési lemma egy olyan lemma, amely a reguláris nyelvek azonos nevű lemmájával analógiával viszonylag könnyen bizonyítja, hogy egy adott nyelv nem kontextusmentes .

Megfogalmazás

Ha L egy CS-nyelv a V ábécé felett, akkor . Vagyis a CS nyelvben bármely kellően hosszú lánc öt részre osztható úgy, hogy a második és negyedik rész tetszőleges számú (talán 0) ismétlése ne vezessen túl a nyelven.
$(\exists n\in \mathbb{N})(\forall \alpha \in L: |\alpha|>n)(\exists 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).$

Bizonyítás

Legyen adott egy CS-nyelv (V, N, S, G), és a nyelv nyelvtana redukálódik (vagyis nem tartalmaz A → ε vagy A → B alakú szabályokat).

Mivel a nem terminális szimbólumok száma véges, csakúgy, mint az egyes következtetési szabályok hossza, a lánc hosszát, amelynél a származékfa magassága nem haladja meg az |N|-t, felülről is korlátozza egy bizonyos szám n.

Nézzünk egy láncot . A fentiek miatt a származtatási fájának magassága meghaladja az |N| a nyelvtan szimbólumai. Mivel minden lépésben egy nem terminális szimbólumot cserélünk, legalább egy nem terminális Q szimbólumot kétszer cserélünk ezen az úton. Ebből következik, hogy van egy xQy lánc, amelynek nem üres x vagy y a Q-ból származtatva. Ezért az S →* α levezetési folyamatban a Q →* xQy levezetési folyamat tetszőlegesen megismételhető vagy elhagyható. $\alpha: |\alpha|>n$

Triviális következmény: bármely végtelen CS-nyelvben van egy végtelen részhalmaza a karakterláncoknak, amelyek hossza növekvő aritmetikai sorozatot alkot.

Használati példák

A nyelv nem CS-nyelv: lehetetlen két láncot kiválasztani és letölteni anélkül, hogy elhagyná a nyelvet (egyszerre három láncot kell letöltenie). $a^nb^nc^n, n \geq 0$
A nyelv szintén nem CS-nyelv, de ezt „pumpálással” már nem lehet majd bizonyítani: fel lehet pumpálni az a és b karakterek „zónáit”, kihasználva, hogy esetleg kevesebb a c karakter. a láncban. De ha figyelembe vesszük a nyelvhez tartozó karakterláncot , akkor vagy a pumpált karakterláncok kizárása kivesz minket a nyelvből, ami ellentmond a pumpáló lemmának. $a^nb^nc^k, n,k \geq 0, k \leq n$ $a^nb^nc^n$
A nyelv szintén nem CF-nyelv, mivel ellentmond a lemma következményének. $a^{n^2}$

Lásd még

Irodalom

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
A. I. Belousov, S. B. Tkacsev. Diszkrét matematika / szerk. d.t.s. prof. V.S. Zarubina, Ph.D. prof. A. P. Kriscsenko. - 4. kiadás, rev. — (matematika műegyetemen). - 2000 példányban. — ISBN 5-708-2886-4.

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus