Lema de Arden
Es importante señalar que existen dos versiones simétricas del lema de Arden. Dependiendo de la versión que use, el método para generar las ecuaciones es ligeramente diferente.
Versión correcta
Considere el siguiente autómata:
La construcción de las ecuaciones se realiza de la siguiente manera: el lenguaje reconocido por un estado es igual al lenguaje seguido por el símbolo de transición de sus predecesores. Por ejemplo, el idioma L2 aceptado por el estado 2 es igual a: L2 = L1Para. Una palabra w ∈ LI si y solo si el
existe un cálculo del autómata en w partiendo del estado inicial y llegando al estado i (atención la versión no es la misma que en la versión izquierda).
Tenemos el siguiente sistema de ecuaciones:
Sustituyendo L1 en la segunda ecuación por su valor entonces L2 en la tercera y cuarta ecuaciones obtenemos:
Aplicamos el lema de Arden correcto a las dos últimas ecuaciones:
El lenguaje reconocido por el autómata es el conjunto de lenguajes reconocidos por sus estados terminales, que en este ejemplo da: ab (a + b) * + (b + aa) a *
Versión izquierda
Considere el siguiente autómata:
La construcción de las ecuaciones se realiza de la siguiente manera: el lenguaje reconocido por un estado es igual al lenguaje precedido por el símbolo de transición de sus sucesores. Por ejemplo, el idioma L2 aceptado por el estado 2 es igual a: L2 = aL1+ aL3+ ε (porque es un estado terminal). Una palabra w ∈ LI si y solo si el
Existe un cálculo del autómata en w partiendo del estado i y llegando a un estado final (tenga cuidado si usamos la otra versión del lema, la definición sería diferente).
Tenemos el siguiente sistema de ecuaciones:
Sustituyendo L3 y yo4 en las dos primeras ecuaciones, entonces L2 en la primera ecuación obtenemos:
Finalmente, aplicando el lema de Arden (versión izquierda) a la primera ecuación,
obtiene: L1 = (a + bba + bbab) ∗ (bb + ε). Aquí tenemos el lenguaje reconocido desde el estado inicial, por lo tanto desde el autómata.
ES 
FR 
EN