Lema de crecimiento para lenguajes libres de contexto

El lema de crecimiento para lenguajes libres de contexto es un lema que, por analogía con el lema del mismo nombre para lenguajes regulares, hace relativamente fácil demostrar que un lenguaje dado no es libre de contexto .

Redacción

Si L es un lenguaje CS sobre el alfabeto V, entonces . En otras palabras, cualquier cadena suficientemente larga en el lenguaje CS se puede dividir en cinco partes para que la repetición de la segunda y cuarta partes un número arbitrario de veces (quizás 0) no lleve a ir más allá del lenguaje.
$(\existe n\en \mathbb{N})(\forall \alpha \in L: |\alpha|>n)(\existe u,x,v,y,w\en V^*):$
$\alpha =uxvyw\land |xy|>0\land |xvy|\leq n\land (\forall i\geq 0:ux^{i}vy^{i}w\in L).$

Prueba

Supongamos que se da un lenguaje CS (V, N, S, G) y se reduce la gramática del lenguaje (es decir, no contiene reglas de la forma A → ε o A → B).

Dado que el número de símbolos no terminales es finito, así como la longitud de cada regla de inferencia, la longitud de la cadena, cuya altura del árbol de derivación no excede |N|, también está limitada desde arriba por un cierto número nm.

Consideremos una cadena . En virtud de lo anterior, la altura de su árbol de derivación excederá |N|, es decir, existirá un camino desde el axioma hasta uno de los símbolos terminales, cuya longitud será mayor que el número de no terminales símbolos de la gramática. Dado que se reemplaza un símbolo no terminal en cada paso, al menos un símbolo Q no terminal se reemplazará dos veces en esta ruta. De esto se deduce que hay una cadena xQy con x o y no vacíos que se derivan de Q. Por lo tanto, en el proceso de derivación S →* α, el proceso de derivación Q →* xQy puede repetirse tantas veces como se desee u omitirse. $\alfa: |\alfa|>n$

Un corolario trivial: en cualquier lenguaje CS infinito hay un subconjunto infinito de cadenas cuyas longitudes forman una progresión aritmética creciente.

Ejemplos de uso

El idioma no es un lenguaje CS: es imposible seleccionar dos cadenas y descargarlas sin salir del idioma (debe descargar tres cadenas al mismo tiempo). $a^nb^nc^n, n \geq 0$
El lenguaje tampoco es un lenguaje CS, pero ya no será posible demostrarlo mediante “bombeo”: puede bombear “zonas” de caracteres a y b, aprovechando que puede haber menos caracteres c en la cadena Pero si consideramos la cadena que pertenece al lenguaje , entonces la exclusión de las cadenas bombeadas nos sacará del lenguaje, lo que contradice el lema de bombeo. $a^nb^nc^k, n,k \geq 0, k \leq n$ $a^nb^nc^n$
El lenguaje tampoco es un lenguaje CF, ya que contradice el corolario del lema. $un^{n^2}$

Véase también

Literatura

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
A. I. Belousov, S. B. Tkachev. Matemática Discreta / ed. d.t.s. profe. VS Zarubina, Ph.D. profe. AP Krishchenko. - 4ª ed., rev. — (matemáticas en una universidad técnica). - 2000 copias. — ISBN 5-708-2886-4.

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
Tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami