Lema de Arden

El Lema de Arden, en lenguajes formales, indica una solución particular a la ecuación con expresiones regulares: ${\displaystyle x=rx+s}$ (en donde ${\displaystyle r}$ y ${\displaystyle s}$ son expresiones regulares conocidas, y ${\displaystyle 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.

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

${\displaystyle x=rx+s}$

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

${\displaystyle x=r^{*}s}$

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

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

En donde ${\displaystyle t}$ es cualquier expresión regular.

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

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

Así mismo, si la ecuación es:

${\displaystyle x=xr+s}$

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

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 ${\displaystyle q}$, al mismo estado ${\displaystyle 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:

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

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

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

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

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