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 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 == |