Prueba

Teor´a de Aut´ matas y Lenguajes Formales ı o Bolet´n de Autoevaluaci´ n 4: ¿C´ mo se calcula la Expresi´ n Regular asociada a un AFD?. ı o o o

1.

Objetivos.

El objetivo de este bolet´n es ilustrar uno de los m´ todos que permiten calcular la expresi´ n regular ı e o que denota el mismo lenguaje que un Aut´ mata Finito reconoce mediante ejemplos y, adem´ s, proporcioo a nar la soluci´ na alguno de los problemas propuestos en el bolet´n para que pod´ is comprobar si hab´ is o ı a e aplicado bien este m´ todo. e

2.

Idea Principal.

Los teoremas de Kleene, el de An´ lisis y el de S´ntesis, establecen la equivalencia entre los AFs a ı y las expresiones regulares. En concreto, el de An´ lisis permite afirmar que dado un AFD, existe una a expresi´ n regular que lo denota. Sudemostraci´ n ya establece un m´ todo para calcular dicha expresi´ n o o e o regular, pero en la pr´ ctica no es el m´ todo que se suele utilizar para realizar dicho c´ lculo. a e a En su lugar, es m´ s aconsejable el uso de la Regla de Arden. Para aplicarla, hay que establecer un a sistema de ecuaciones lineales en expresiones regulares y resolverlo. Cada ecuaci´ n de un sistema de o ecuacioneslineales en expresiones regulares tiene la siguiente forma general X = rX + s en la que r y s son expresiones regulares sobre un alfabeto Σ. Dependiendo de que λ ∈ r o λ ∈ r se tienen dos soluciones para dicha ecuaci´ n: o - λ ∈ r y, entonces, X = r∗ s. Para comprobarlo, basta ver que X = rX + s = r(r∗ s) + s = (rr∗ + λ)s = r∗ s = X. - λ ∈ r y, entonces, hay infinitas soluciones X = r∗ (s + t), dondet es una expresi´ n regular cualo quiera sobre Σ (normalmente, este caso no nos afectar´ ). Este resultado puede comprobarse de la a siguiente forma, X = rX + s = r(r∗ (s + t)) + s = (rr∗ + λ)s + rr∗ t = (r+ + λ)s + r+ t. Como r∗ = r+ si λ ∈ r, entonces lo anterior queda, (r+ + λ)s + r+ t = (r∗ + λ)s + r∗ t = r∗ (s + t) = X.

3.

M´ todo para obtener la Expresi´ n regular que denota a un AFdado. e o

El m´ todo se basa en el establecimiento de un sistema de ecuaciones lineales en expresiones regulares e a partir del AF. Sea A, A = Σ, Q, f, q0 , F 1

un AFD o un AFN; a A se le puede asociar un sistema de ecuaciones lineales en expresiones regulares de la siguiente forma: 1. 2. 3. Se asocia una variable a cada estado: ∀qi ∈ Q, se le asocia Xi . Las ecuaciones se construyen enfunci´ n de las transiciones: si qj ∈ f (qi , a), entonces en la o ecuaci´ n de la variable Xi aparece el t´ rmino aXj en su parte derecha: Xi = ... + aXj + .... o e Adem´ s, se asocia el t´ rmino λ a los estados finales: si qi ∈ F , entonces en la ecuaci´ n de la a e o variable Xi aparece λ en su parte derecha: Xi = ... + λ + .... El lenguaje reconocido por el AF es la expresi´ n regular de la variableasociada a su estado inicial. o

3.1. Ejemplo 1.
Hay que calcular la expresi´ n regular que denota el lenguaje reconocido por el aut´ mata que se o o muestra en la siguiente figura:
X3
0

q3
1 1 1 0 0

X1
0, 1

q1

q2 X2

X0

q0

Sobre la figura se ha asociado ya a cada estado su correspondiente variable. De acuerdo al segundo y tercer paso del m´ todo, el sistema de ecuacioneslineales que hay que resolver es el siguiente: e X0 X1 X2 X3 = 0X1 + 1X1 + λ = (0 + 1)X1 + λ = 0X2 + 1X3 + λ = 1X2 + 0X1 = 0X3 + 1X1

´ Recordemos que la soluci´ n de la ecuaci´ n general, X = rX + s es X = r∗ s. En la ultima ecuaci´ n, o o o si identificamos t´ rminos con r y s se tiene: e X3 = 0 X3 + 1X1 .
r s

Por lo tanto, X3 = 0∗ 1X1 .

2

De forma similar, se puede operar con X2 ,X2 = 1 X2 + 0X1 , ⇒ X2 = 1∗ 0X1 .
r s

Se tienen X2 y X3 en funci´ n de X1 . Al substituir en la ecuaci´ n de X1 se obtiene o o X1 = 0X2 + 1X3 + λ = 01∗ 0X1 + 10∗ 1X1 + λ = (01∗ 0 + 10∗ 1)X1 + λ Agrupando t´ rminos se llega a e X1 = (01∗ 0 + 10∗ 1) X1 + λ , ⇒ X1 = (01∗ 0 + 10∗ 1)∗ λ = (01∗ 0 + 10∗ 1)∗ .
r s

y, al substituir en la ecuaci´ n de X0 se obtiene finalmente, o X0 = (0 + 1)X1 + λ...