Todos los lengajes no son regulares

Solo disponible en BuenasTareas
  • Páginas : 3 (560 palabras )
  • Descarga(s) : 0
  • Publicado : 2 de mayo de 2011
Leer documento completo
Vista previa del texto
Todos los lenguajes no son regulares, simplemente hay que
tener en cuenta que los lenguajes regulares son definidos por
una expresión, cuando la intuición nos dice que se pueden
definir lenguajesde una forma más compleja.
No hay ningún método que nos permita decidir si un lenguaje
es regular o no, ya que depende de la descripción del lenguaje.
Aunque si que tenemos diferentes herramientasque permiten
probar que lenguajes específicos no son regulares.

Recordad que, usando las propiedades de las expresiones
regulares, toda expresión regular se puede poner en forma
disyuntivanormal y esto nos da una idea de como se puede
generar palabras a partir de unas conocidas.

Recordad que en las expresiones regulares que generan
lenguajes con infinitas palabras incluyen el operadorestrella.
Por lo que si tenemos una palabra, hay formas de generar
infinitas nuevas.

Lema del bombeo para lenguajes regulares
En la teoría de lenguajes formales, el lema del bombeo paralenguajes regulares describe una propiedad esencial de todo lenguaje regular. Informalmente, dice que cualquier palabra suficientemente larga en un lenguaje regular puede ser bombeada - eso es, repetir unasección en la mitad de la palabra un número arbitrario de veces - para producir una nueva palabra que también pertenece al mismo lenguaje.
El lema de bombeo fue enunciado por primera vez por Y.Bar-Hillel, M. Perles, E. Shamir en 1961.[1] Es útil para demostrar que un lenguaje específico no es regular.

Enunciado formal
Sea L un lenguaje regular. Entonces existe un entero (al que llamaremos"longitud de bombeo" y que dependerá exclusivamente de L) tal que cualquier cadena w perteneciente a L, de longitud mayor o igual que p, puede ser escrita como w = xyz (p. ej. dividiendo w en tressubcadenas), de forma que se satisfacen las siguientes condiciones:
| y | > 0

y es la subcadena que puede ser bombeada (borrada o repetida un número i de veces como se indica en (3), y la cadena...
tracking img