Resolviendo por el lema de Arden

Dificultad
Duro 80%

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.

lema de & #039; Arden

Versión correcta

Considere el siguiente autómata:

lema de & #039; Arden

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:

lema de & #039; Arden

Sustituyendo L1 en la segunda ecuación por su valor entonces L2 en la tercera y cuarta ecuaciones obtenemos:

lema de & #039; Arden

Aplicamos el lema de Arden correcto a las dos últimas ecuaciones:

lema de & #039; Arden

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:

lema de & #039; Arden

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:

lema de & #039; Arden

Sustituyendo L3 y yo4 en las dos primeras ecuaciones, entonces L2 en la primera ecuación obtenemos:

lema de & #039; Arden

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.

Compartir, repartir
es_ESES