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 54: | Línea 54: | ||
== Lema de Pumping (LIC) == | == Lema de Pumping (LIC) == | ||
=== Altura del | === Altura del arbol === | ||
La altura del | La altura del arbol de derivacion es la longitud del camino más largo en el arbol de derivacion tal que comienza en la raiz y el final es una hoja (definicion natural de arbol). Vale que la hoja siempre es un terminal. Notar que en el arbol de derivacion, la base (hojas leidas en preorder) es igual a la cadena derivada. | ||
Sea una gramatica donde | Sea una gramatica donde ''a'' es la longitud del lado derecho más largo entre todas las producciones. Dado un arbol T para una cadena alfa, vale que <math>| \alpha | \leq a^h</math>, donde ''h'' es la altura del arbol. | ||
La | La demostracion se hace por induccion sobre la altura. El caso base con h = 0 es trivial. El paso inductivo se basa que la base correspondiente a la altura ''h'', llamemosla <math>\gamma</math>, cumple la HI; y como <math>\alpha</math> se deriva a partir de <math>\gamma</math> expandiendo a lo sumo <math>| \gamma |</math> simbolos no terminales, entonces <math>| \alpha | \leq a * | \gamma |</math>. | ||
=== Pumping (LIC) === | === Pumping (LIC) === | ||
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| < |V_N|+1 </math>. | |||
La respuesta es sencilla, si recorremos el árbol de derivación que genera esa cadena (de abajo hacia arriba) buscando la primer repetición de A la cantidad MÁXIMA de no terminales que tenemos que recorrer es <math>|V_N|+1 </math>. | |||
La respuesta es sencilla, recorremos el árbol de abajo hacia arriba buscando la | |||
== Decidibilidad == | == Decidibilidad == | ||
Línea 440: | Línea 438: | ||
<br/><math>A' \rightarrow \beta _1 | \beta _2</math> | <br/><math>A' \rightarrow \beta _1 | \beta _2</math> | ||
Notar que a pesar de los algoritmos para eliminar factorización y recursividad a izquierda, puede haber lenguajes para los que no haya una gramática LL(1) que los reconozca (por ejemplo, cualquier lenguaje libre de contexto no determinístico, como ser | Notar que a pesar de los algoritmos para eliminar factorización y recursividad a izquierda, puede haber lenguajes para los que no haya una gramática LL(1) que los reconozca (por ejemplo, cualquier lenguaje libre de contexto no determinístico, como ser wwr). | ||
=== ASDP Recursivo === | === ASDP Recursivo === |