Edición de «Demostraciones (Teoría de Lenguajes)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 66: | Línea 66: | ||
El lema de pumping para LIC es similar al de gramaticas regulares. La idea es que para toda cadena que supere una longitud critica ''n'' del lenguaje (puede tomarse <math>a^{|V_N|+1}</math>), la cadena pueda descomponerse en 5 partes ''r,x,y,z,s'' tal que puedan insertarse tantas repeticiones de ''x'' y ''z'' como se desee y que la cadena se mantenga en el lenguaje. Se pide ademas que la longitud de ''x+z'' sea no nula (para que haya algo a insertar) y que ''x+y+z'' no supere a '''n'''. | El lema de pumping para LIC es similar al de gramaticas regulares. La idea es que para toda cadena que supere una longitud critica ''n'' del lenguaje (puede tomarse <math>a^{|V_N|+1}</math>), la cadena pueda descomponerse en 5 partes ''r,x,y,z,s'' tal que puedan insertarse tantas repeticiones de ''x'' y ''z'' como se desee y que la cadena se mantenga en el lenguaje. Se pide ademas que la longitud de ''x+z'' sea no nula (para que haya algo a insertar) y que ''x+y+z'' no supere a '''n'''. | ||
La demostracion parte de una cadena <math>\alpha</math> y un arbol de derivacion minimo T (es decir, de altura minima). Usando el lema anterior, puede probarse que <math>a^h \geq | \alpha| \geq n = a^{|V_N|+1}</math>, lo que lleva a que <math>h \geq |V_N|+1</math>. | |||
En otras palabras, si la cadena es lo suficientemente grande, entonces la altura del arbol que la genera sera mayor estricto a la cantidad de simbolos no terminales que tiene la gramatica. Por lo tanto, recorriendo la rama mas larga del arbol, debe haber por lo menos un no terminal repetido (supongamos ''A''). | En otras palabras, si la cadena es lo suficientemente grande, entonces la altura del arbol que la genera sera mayor estricto a la cantidad de simbolos no terminales que tiene la gramatica. Por lo tanto, recorriendo la rama mas larga del arbol, debe haber por lo menos un no terminal repetido (supongamos ''A''). | ||
Línea 76: | Línea 76: | ||
Esto significa que ''A'' deriva (en uno o mas pasos) tanto en ''y'' como en ''xyz'', y que ''S'' deriva en ''rAs''. Haciendo induccion en la cantidad de apariciones de ''x'' y ''z'' (caso base es cero) es sencillo ver que ''A'' termina derivando en ''xAz'' o ''y'', con lo que <math>r x^i y z^i s</math> es forma sentencial del lenguaje. | Esto significa que ''A'' deriva (en uno o mas pasos) tanto en ''y'' como en ''xyz'', y que ''S'' deriva en ''rAs''. Haciendo induccion en la cantidad de apariciones de ''x'' y ''z'' (caso base es cero) es sencillo ver que ''A'' termina derivando en ''xAz'' o ''y'', con lo que <math>r x^i y z^i s</math> es forma sentencial del lenguaje. | ||
'''NOTA''': Un detalle importante que se toma en el final (y que no queda tan claro en los apuntes) es la justificación de que <math>|xyz| \leq |V_N|+1 </math> (en el dibujo es vwx). | |||
'''NOTA''': Un detalle importante que se toma en el final (y que no queda tan claro en los apuntes) es la justificación de que <math>|xyz| \leq | |||
La respuesta es sencilla, recorremos el árbol de abajo hacia arriba buscando la segunda aparición de A, la cantidad MÁXIMA de no terminales por los que tenemos que pasar hasta encontrar el primer repetido es <math>|V_N|+1 </math>. Esa es la justificación por la que podemos afirmar que ese subárbol tiene esa altura y de ahí acotar la longitud de <math>xyz</math>. | La respuesta es sencilla, recorremos el árbol de abajo hacia arriba buscando la segunda aparición de A, la cantidad MÁXIMA de no terminales por los que tenemos que pasar hasta encontrar el primer repetido es <math>|V_N|+1 </math>. Esa es la justificación por la que podemos afirmar que ese subárbol tiene esa altura y de ahí acotar la longitud de <math>xyz</math>. | ||