Lema de creștere pentru limbi fără context

Lema de creștere pentru limbile fără context este o lemă care, prin analogie cu lema cu același nume pentru limbile obișnuite, face relativ ușor să se demonstreze că o anumită limbă nu este lipsită de context .

Formulare

Dacă L este o limbă CS peste alfabetul V, atunci . Cu alte cuvinte, orice lanț suficient de lung în limbajul CS poate fi împărțit în cinci părți, astfel încât repetarea părții a doua și a patra de un număr arbitrar de ori (poate 0) să nu conducă la depășirea limbii.
$(\există n\în \mathbb{N})(\forall \alpha \in L: |\alpha|>n)(\există 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).$

Dovada

Să fie dat un limbaj CS (V, N, S, G), iar gramatica limbii este redusă (adică nu conține reguli de forma A → ε sau A → B).

Deoarece numărul simbolurilor neterminale este finit, precum și lungimea fiecărei reguli de inferență, lungimea lanțului, înălțimea arborelui de derivare pentru care nu depășește |N|, este, de asemenea, limitată de sus de un anumit numărul n.

Să luăm în considerare un lanț . În virtutea celor de mai sus, înălțimea arborelui său de derivare va depăși |N|, adică va exista o cale de la axiomă la unul dintre simbolurile terminale, a cărui lungime va fi mai mare decât numărul de non-terminale. simboluri ale gramaticii. Deoarece un simbol non-terminal este înlocuit la fiecare pas, cel puțin un simbol Q non-terminal va fi înlocuit de două ori pe această cale. De aici rezultă că există un lanț xQy cu x sau y nevid care derivă din Q. Prin urmare, în procesul de derivare S →* α, procesul de derivare Q →* xQy poate fi repetat de câte ori se dorește sau omis. $\alpha: |\alpha|>n$

Un corolar trivial: în orice limbaj CS infinit există un subset infinit de șiruri ale căror lungimi formează o progresie aritmetică crescândă.

Exemple de utilizare

Limba nu este o limbă CS: este imposibil să selectați două lanțuri și să le descărcați fără a părăsi limba (trebuie să descărcați trei lanțuri în același timp). $a^nb^nc^n, n \geq 0$
Nici limbajul nu este un limbaj CS, dar nu se va mai putea demonstra acest lucru prin „pompare”: puteți pompa „zone” de caractere a și b, profitând de faptul că pot fi mai puține caractere c. în lanț. Dar dacă luăm în considerare șirul aparținând limbajului , atunci fie excluderea șirurilor pompate ne va scoate din limbaj, ceea ce contrazice lema de pompare. $a^nb^nc^k, n,k \geq 0, k \leq n$ $a^nb^nc^n$
De asemenea, limba nu este un limbaj CF, deoarece contrazice corolarul lemei. $a^{n^2}$

Vezi și

Literatură

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M .: „Williams” , 2002. - S. 528. - ISBN 0-201-44124-1 .
A.I. Belousov, S.B. Tkaciov. Matematică discretă / ed. d.t.s. prof. V.S. Zarubina, Ph.D. prof. A.P. Krishcenko. - Ed. a IV-a, rev. — (matematică la o universitate tehnică). - 2000 de exemplare. — ISBN 5-708-2886-4.

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tip 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami