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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma} 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 ( Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_1}Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_2} ) o la concatenacion ( Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_1}Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_2} ) de dos lenguajes regulares
  • L es la clausura o estrella de Kleene ( Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_1} * ) 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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma^*} es cerrado respecto de la unión. Dados Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_1} = Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L(M_1)} y Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_2} = Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L(M_2)} , Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_1}Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_2} 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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle ER(L_1)+ER(L_2)} es regular y la operación + es equivalente a la unión de los lenguajes Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_1} y Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_2} .
  • 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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Delta} es el alfabeto del autómata y queremos tomar el complemento respecto a un superconjunto Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma} de Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Delta} , basta con encontrar el autómata del complemento Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle M'} y calcular: Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L(M') \cup \Sigma^*(\Sigma - \Delta)\Sigma^*} (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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}} .

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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (a, b)} es final si Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a} y Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle b} 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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a^k b^k} )

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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k} tal que Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 2n > k \geq n} , donde Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n} 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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (L_1 \cap \overline{L_2}) \cup (\overline{L_1} \cap L_2)} . Si es vacío, son equivalentes, sino no lo son.