Vækstlemma for kontekstfrie sprog

Vækstlemmaet for kontekstfrie sprog er et lemma, der analogt med lemmaet af samme navn for regulære sprog gør det relativt nemt at bevise, at et givet sprog ikke er kontekstfrit .

Ordlyd

Hvis L er et CS-sprog over alfabetet V, så . Med andre ord kan enhver tilstrækkelig lang kæde i CS-sproget opdeles i fem dele, således at gentagelsen af anden og fjerde del et vilkårligt antal gange (måske 0) ikke fører til at gå ud over sproget.
$(\eksisterer n\i \mathbb{N})(\forall \alpha \i L: |\alpha|>n)(\eksisterer u,x,v,y,w\i V^*):$
$\alpha =uxvyw\land |xy|>0\land |xvy|\leq n\land (\forall i\geq 0:ux^{i}vy^{i}w\in L).$

Bevis

Lad et CS-sprog (V, N, S, G) angives, og sprogets grammatik reduceres (det vil sige, at det ikke indeholder regler af formen A → ε eller A → B).

Da antallet af ikke-terminale symboler er begrænset, såvel som længden af hver inferensregel, er længden af kæden, hvor højden af afledningstræet ikke overstiger |N|, også begrænset ovenfra af en vis nummer n.

Lad os overveje en kæde . I kraft af ovenstående vil højden af dets afledningstræ overstige |N|, det vil sige, at der vil være en sti fra aksiomet til et af terminalsymbolerne, hvis længde vil være større end antallet af ikke-terminale grammatikkens symboler. Da et ikke-terminalt symbol udskiftes ved hvert trin, vil mindst ét ikke-terminalt Q-symbol blive erstattet to gange i denne vej. Det følger heraf, at der er en kæde xQy med ikke-tom x eller y, der stammer fra Q. Derfor kan afledningsprocessen Q →* xQy i afledningsprocessen S →* α gentages så mange gange som ønsket eller udelades. $\alpha: |\alpha|>n$

En triviel konsekvens: i ethvert uendeligt CS-sprog er der en uendelig delmængde af strenge, hvis længder danner en stigende aritmetisk progression.

Eksempler på brug

Sproget er ikke et CS-sprog: det er umuligt at vælge to kæder og downloade dem uden at forlade sproget (du skal downloade tre kæder på samme tid). $a^nb^nc^n, n \geq 0$
Sproget er heller ikke et CS-sprog, men det vil ikke længere være muligt at bevise dette ved at "pumpe": du kan pumpe "zoner" af tegn a og b op, og udnytte det faktum, at der kan være færre c-tegn i kæden. Men hvis vi betragter strengen, der hører til sproget , så vil enten udelukkelsen af pumpede strenge tage os ud af sproget, hvilket modsiger det pumpende lemma. $a^nb^nc^k, n,k \geq 0, k \leq n$ $a^nb^nc^n$
Sproget er heller ikke et CF-sprog, da det strider mod lemmaets følge. $a^{n^2}$

Se også

Litteratur

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion til automatteori, sprog og beregning. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
A.I. Belousov, S.B. Tkachev. Diskret matematik / red. d.t.s. prof. V.S. Zarubina, Ph.D. prof. A.P. Krishchenko. - 4. udg., rev. — (matematik ved et teknisk universitet). - 2000 eksemplarer. — ISBN 5-708-2886-4.

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