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 .
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.
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.
Un corolar trivial: în orice limbaj CS infinit există un subset infinit de șiruri ale căror lungimi formează o progresie aritmetică crescândă.
Limbi formale și gramatici formale | |
---|---|
Concepte generale | |
Tip 0 | |
Tipul 1 |
|
Tip 2 | |
Tip 3 | |
analizare |