Lema de Arden

El Lema de Arden, en lenguajes formales, indica una solución particular a la ecuación con expresiones regulares: $x=rx+s$ (en donde $r$ y $s$ son expresiones regulares conocidas, y $x$ es desconocida).

Esta solución provee un Algoritmo sistemático y metódico para la conversión de Autómata finito a Expresión regular.

Enunciado

Sea $\lambda$ la cadena vacía, $r$ y $s$ son expresiones regulares conocidas, y $x$ desconocida. Entonces la ecuación

$x=rx+s$

Tiene una solución única si $\lambda \notin L(r)$. Y esta solución es:

$x=r^{*}s$

Pero si $\lambda \in L(r)$, la ecuación tiene infinitas soluciones:

$x=r^{*}(s+t)$

En donde $t$ es cualquier expresión regular.

Demostración

Sea $x=r^{*}s$ la hipótesis. Se demostrará que $x=rx+s$

$x=r^{*}s=(r^{*})s=(rr^{*}+\lambda )s=rr^{*}s+\lambda s=rr^{*}s+s=r(r^{*}s)+s=rx+s$

Generalizaciones

Así mismo, si la ecuación es:

$x=xr+s$

La solución, si $\lambda \notin L(r)$ es: $x=r^{*}s$

Aplicaciones

Conversión de AFD a expresión regular

Para convertir un Autómata finito determinista (e incluso uno No Determinista, y hasta uno con transiciones nulas) a una Expresión regular, se debe definir un sistema de ecuaciones, este sistema, tendrá tantas incógnitas como estados haya en el autómata que se desea convertir, si el autómata tiene ciclos de longitud 1 (es decir, arcos que van de un estado $q$, al mismo estado $q$), se debe usar el lema de Arden para resolver el sistema de ecuaciones. Cuando todas las incógnitas han sido encontradas, se obtendrá la expresión regular que describe al lenguaje aceptado por el autómata.

Para construir las ecuaciones, se plantean las siguientes incógnitas:

$X_{i}$ es una incógnita que representa una expresión regular que define todas aquellas cadenas que van del estado $q_{i}$ a algún estado final del autómata.

Entonces, por cada estado $q_{i}$ en el autómata, se formará la ecuación:

$X_{i}=\sum {\sigma _{j}X_{j}}$

Donde $\sigma _{j}\in \Sigma$ representa la letra que une mediante un arco al estado $q_{i}$ con el estado $q_{j}$.

Debe agregarse la cadena nula si el estado $q_{i}$ es final.

• Datos: Q670618