bolAuto4

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

1.

Objetivos.

El objetivo de este bolet´ın es ilustrar uno de los m´etodos que permiten calcular la expresi´on regular
que denota el mismo lenguaje que un Aut´omata Finito reconoce mediante ejemplos y, adem´as, proporcionar la soluci´on a alguno de los problemaspropuestos en el bolet´ın para que pod´ais comprobar si hab´eis
aplicado bien este m´etodo.

2.

Idea Principal.

Los teoremas de Kleene, el de An´alisis y el de S´ıntesis, establecen la equivalencia entre los AFs
y las expresiones regulares. En concreto, el de An´alisis permite afirmar que dado un AFD, existe una
expresi´on regular que lo denota. Su demostraci´on ya establece un m´etodo paracalcular dicha expresi´on
regular, pero en la pr´actica no es el m´etodo que se suele utilizar para realizar dicho c´alculo.
En su lugar, es m´as aconsejable el uso de la Regla de Arden. Para aplicarla, hay que establecer un
sistema de ecuaciones lineales en expresiones regulares y resolverlo. Cada ecuaci´on de un sistema de
ecuaciones lineales en expresiones regulares tiene la siguiente formageneral
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´on:
- λ ∈ 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), donde t es una expresi´on regular cualquiera sobre Σ (normalmente,este caso no nos afectar´a). Este resultado puede comprobarse de la
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´etodo para obtener la Expresi´on regular que denota a un AF dado.

El m´etodo se basa en el establecimiento de un sistema deecuaciones lineales en expresiones regulares
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.

Se asocia una variable a cada estado: ∀qi ∈ Q, se le asocia Xi .

2.

Las ecuaciones se construyen en funci´on de las transiciones: si qj ∈ f (qi , a), entonces en la
ecuaci´on de lavariable Xi aparece el t´ermino aXj en su parte derecha: Xi = ... + aXj + ....

3.

Adem´as, se asocia el t´ermino λ a los estados finales: si qi ∈ F , entonces en la ecuaci´on de la
variable Xi aparece λ en su parte derecha: Xi = ... + λ + ....
El lenguaje reconocido por el AF es la expresi´on regular de la variable asociada a su estado inicial.

3.1.

Ejemplo 1.

Hay que calcular la expresi´onregular que denota el lenguaje reconocido por el aut´omata que se
muestra en la siguiente figura:
X3

0

q3
1

X1

1

1

q1

0

q2

0

X2

0, 1

X0

q0

Sobre la figura se ha asociado ya a cada estado su correspondiente variable. De acuerdo al segundo
y tercer paso del m´etodo, el sistema de ecuaciones lineales que hay que resolver es el siguiente:
X0
X1
X2
X3

= 0X1 + 1X1 + λ = (0 + 1)X1 + λ
= 0X2 +1X3 + λ
= 1X2 + 0X1
= 0X3 + 1X1

Recordemos que la soluci´on de la ecuaci´on general, X = rX + s es X = r∗ s. En la u´ ltima ecuaci´on,
si identificamos t´erminos con r y s se tiene:
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´on de X1 . Al substituir en la ecuaci´on de X1 seobtiene
X1 = 0X2 + 1X3 + λ = 01∗ 0X1 + 10∗ 1X1 + λ = (01∗ 0 + 10∗ 1)X1 + λ
Agrupando t´erminos se llega a
X1 = (01∗ 0 + 10∗ 1) X1 + λ , ⇒ X1 = (01∗ 0 + 10∗ 1)∗ λ = (01∗ 0 + 10∗ 1)∗ .
s

r

y, al substituir en la ecuaci´on de X0 se obtiene finalmente,
X0 = (0 + 1)X1 + λ = (0 + 1)(01∗ 0 + 10∗ 1)∗ + λ,
⇒ L(AF D) = (0 + 1)(01∗ 0 + 10∗ 1)∗ + λ.

3.2.

Ejemplo 2.

El siguiente ejemplo es el mismo que...