title: Lema de Arden
text: # 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.
  
  # Lema de Arden
  ## 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.
  
  # Lema de Arden
  ## Enunciado
  ### 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$
  
  # Lema de Arden
  ## Enunciado
  ### Generalizaciones
  
  Así mismo, si la ecuación es:
  $x=xr+s$
  La solución, si $\lambda \notin L(r)$ es: $x=sr^{*}$
  
  # Lema de Arden
  ## 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