Lenguajes regulares

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Existen varias definiciones de lenguajes regulares y todas son equivalentes entre si. Una de la más simples es:

Un lenguaje L sobre un alfabeto dado es regular si y solo si cumple con alguna de las siguientes condiciones:

  • L es finito (la cantidad de palabras es finita, incluyendo el caso de que no tenga palabras)
  • L es la union ( ) o la concatenacion ( ) de dos lenguajes regulares
  • L es la clausura o estrella de Kleene ( * ) de un lenguaje regular

Otra que es de importancia para probar muchas propiedades es:

Un lenguaje es regular cuando existe una gramática regular, o una construcción equivalente, que lo genere.

Propiedades[editar]

Unión[editar]

El conjunto de lenguajes regulares incluido en es cerrado respecto de la unión. Dados = y = , es un lenguaje regular.

  • La demostración es inmediata por el segundo punto de la primera definición. La primera definición es lo mismo a considerar expresiones regulares, ya que el lenguaje generado por es regular y la operación + es equivalente a la unión de los lenguajes y .
  • Utilizando autómatas, basta con crear un AFND-λ compuesto por los dos autómatas que generan los dos lenguajes. La composición se realiza de tal manera que el estado inicial de la maquina resultante tenga transiciones λ a los estados iniciales de las otras dos maquinas. El conjunto de los estados finales de la maquina resultante es la unión de los estados finales de las otras dos maquinas.

Complemento[editar]

El complmento de un lenguaje regular es regular

  • Una forma constructiva de probar esto es tomando el AFD del lenguaje y complementando el conjunto de estados finales (poniendo los finales como no finales y vicevera). Es inmediato que esto genera el complemento. Si es el alfabeto del autómata y queremos tomar el complemento respecto a un superconjunto de , basta con encontrar el autómata del complemento y calcular: (notar que es una unión de lenguajes regulares). Recordar que el AFD debe estar completo (tener el estado "trampa").

Intersección[editar]

La intersección de un lenguaje regular es regular

Es inmediata usando la ley de DeMorgan, ya que .

También se puede realizar de forma constructiva a partir de los autómatas. Se arma un gran autómata que tiene como estados el producto cartesiano de los estados de los otros dos de forma tal que un estado es final si y son finales en sus respectivos autómatas.

Unión e Intersección finita[editar]

La unión finita y la intersección finita de lenguajes regulares dan por resultado un leguaje regular. Es trivial de probar con una inducción.

Esto NO VALE para INFINITO. (pensar en la unión infinita de )

Problemas decidibles[editar]

Pertenencia[editar]

Saber si una cadena pertenece a un lenguaje regular es decidible (Dado el lenguaje regular, se construye su AFD y se pone a prueba la cadena).

Finitud[editar]

Todo lenguaje finito es regular. Ya que se puede ver como la unión finita de los elementos uno a uno.

Determinar si un lenguaje regular es finito es decidible

Un lenguaje regular es finito si en su AFD ningún estado desde el cual se pueda alcanzar un estado final puede dar lugar a un "ciclo".

Alternativamente, un lenguaje regular es infinito sii su AFD acepta al menos una cadena de longitud tal que , donde es la cantidad de estados del AFD.

Vacuidad[editar]

Determinar si un lenguaje regular es vacío es decidible. Se construye el AFD y se mira si alguno de los estados alcanzables es final.

Equivalencia[editar]

Determinar si dos lenguajes regulares son equivalentes es decidible. Se construyen sus respectivos autómatas. Luego se construye el autómata de . Si es vacío, son equivalentes, sino no lo son.