Edición de «Demostraciones Lenguajes Regulares (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 105: | Línea 105: | ||
Se demuestra primero el lema <math>A \Rightarrow^* wB \Leftrightarrow q_B \in \delta(q_A,w)</math> por inducción en <math>w</math>: | Se demuestra primero el lema <math>A \Rightarrow^* wB \Leftrightarrow q_B \in \delta(q_A,w)</math> por inducción en <math>w</math>: | ||
* El caso base <math>w = \lambda</math> es aútomático, porque si <math>w</math> es vacia, <math>B</math> tiene que ser <math>A</math> (por las producciones que puede tener la gramática) y por definición de <math>\delta</math> también se cumple lo otro. | * El caso base <math>w = \lambda</math> es aútomático, porque si <math>w</math> es vacia, <math>B</math> tiene que ser <math>A</math> (por las producciones que puede tener la gramática) y por definición de <math>\delta</math> también se cumple lo otro. | ||
* Luego se prueba para <math>w = \alpha a</math>. Se ve que si <math>A \Rightarrow^* \alpha | * Luego se prueba para <math>w = \alpha a</math>. Se ve que si <math>A \Rightarrow^* \alpha(aB)</math>, de <math>q_A</math> se puede llegar a <math>q_C</math> por <math>\alpha</math> por hip. inductiva, y que de <math>q_C</math> se puede llegar a <math>q_B</math> por <math>a</math> por la regla 4 de la definición de <math>M</math>. Entonces de <math>q_A</math> se puede llegar a <math>q_B</math> por <math>\alpha a</math>. | ||
Después se debe probar que el lenguaje generado por <math>G</math> y <math>M</math> es el mismo: | Después se debe probar que el lenguaje generado por <math>G</math> y <math>M</math> es el mismo: | ||
Línea 213: | Línea 213: | ||
Como <math>q_{i_j} = q_{i_k}</math> y por la propiedad ya demostrada, es posible repetir ''y'' tantas veces como se desee y volver siempre al mismo estado, que tras consumir la cadena ''z'' se sabe que lleva a un estado final con lo que la cadena resulta aceptada. | Como <math>q_{i_j} = q_{i_k}</math> y por la propiedad ya demostrada, es posible repetir ''y'' tantas veces como se desee y volver siempre al mismo estado, que tras consumir la cadena ''z'' se sabe que lleva a un estado final con lo que la cadena resulta aceptada. | ||
El lema de pumping es una manera útil de | El lema de pumping es una manera útil de determinar si un lenguaje es regular o no. Si no verifica este lema, entonces se sabe que no es regular. Notar que la implicación no vale a la inversa, esto es, un lenguaje no regular puede cumplir pumping de regulares. En estos casos generalmente se recurre a demostrar que el complemento, inverso, unión o alguna combinación a partir de dicho lenguaje no lo verifica. | ||
== Minimizacion == | == Minimizacion == |