Arden Lemma
Es importante notar que hay dos versiones simétricas del lema de Arden. Dependiendo de la versión que utilice, 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 comenzando desde el estado inicial y llegando al estado i (nótese que la versión no es la misma en una 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 derecho de Arden a las dos últimas ecuaciones:
El lenguaje reconocido por el autómata es el conjunto de lenguajes reconocidos por sus estados terminales, lo que da en este ejemplo: 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,
se obtiene: L1 = (a + bba + bbab)∗ (bb + ε). Tenemos aquí el lenguaje reconocido desde el estado inicial, por tanto desde el autómata.
