Lema d'Ardixen

El Lema d'Ardixen, en llenguages formals, indica una solució particular a l'equació en expressions regulars: $x=rx+s$ (en a on $r$ i $s$ són expressions regulars conegudes, i $x$ és desconeguda).

Esta solució proveïx un Algoritme sistemàtic i metòdic per a la conversió d'Autómata finito a Expressió regular.

Enunciat

Siga $\lambda$ la cadena buida, $r$ i $s$ són expressions regulars conegudes, i $x$ desconeguda. Llavors l'equació

$x=rx+s$

Té una solució única si $\lambda \notin L(r)$. I esta solució és:

$x=r^{*}s$

Pero si $\lambda \in L(r)$, l'equació té infinites solucions:

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

En a on $t$ és qualsevol expressió regular.

Demostració

Siga $x=r^{*}s$ l'hipòtesis. Es demostrarà que $x=rx+s$

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

Generalisacions

Aixina mateix, si l'equació és:

$x=xr+s$

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

Aplicacions

Conversió de AFD a expressió regular

Per a convertir un Autómata finito determinista (i inclús un No Determinista, i fins a un en transicions nules) a una Expressió regular, es deu definir un sistema d'equacions, este sistema, tindrà tantes incògnites com a estats hi haja en l'autómata que es desija convertir, si l'autómata té cicles de llongitut 1 (és dir, arcs que van d'un estat $q$, al mateix estat $q$), es deu usar el lema d'Ardixen per a resoldre el sistema d'equacions. Quan totes les incògnites han segut trobades, s'obtindrà l'expressió regular que descriu al llenguage acceptat per l'autómata.

Per a construir les equacions, es plantegen les següents incògnites:

$X_i$ és una incògnita que representa una expressió regular que definix totes aquelles cadenes que van de l'estat $q_i$ a algun estat final de l'autómata.

Llavors, per cada estat $q_i$ en l'autómata, es formarà l'equació:

$X_i=\sum {\sigma }_j{X}_j$

A on ${\sigma }_j\in \Sigma$ representa la lletra que unix per mig de un arc a l'estat $q_i$ en l'estat $q_j$.

Deu agregar-se la cadena nula si l'estat $q_i$ és final.