INTRODUCCIÓN
Los diagramas de transición son una
instrumentación de un modelo formal denominado autómatas finitos, conocidos
también como máquinas de estado finito o máquinas secuénciales.
Los autómatas finitos
vienen en diferentes tipos:
·
· No determinísticos
(AFN) el autómata puede
estar en varios estados simultáneamente.
Los autómatas finitos no determinísticos pueden ser “compilados” a
autómatas finitos determinísticos por medio de un algoritmo.
·
· Deterministicos
(AFD) el autómata únicamente puede estar en un estado en un momento determinado.
Un autómata finito es un conjunto de estados y un control que se mueve de
un estado a otro en respuesta a entradas externas.
Existe otro tipo de autómata finito que amplia los no determinísticos
permitiendo el paso de un estado a otro espontáneamente por medio de
transiciones con la cadena vacía.
Estos últimos aceptan el mismo tipo de lenguajes (regulares).
CONVERTIR
UN DIAGRAMA NO DETERMINISTA EN UNO DETERMINISTA
TEOREMA. Dado un AFND M = ( ∑,Q, I, F,
δ ), se puede construir un AFN M‘ equivalente a M, es decir, tal que L(M) = L(M‘)
Cojamos el
diagrama del siguiente
autómata para el
alfabeto ∑ = {a, b}. Como podemos ver, no es determinista pues
desde el estado 1 salen dos arcos rotulados con b y del estado 2 salen dos
arcos etiquetados con a.
Para convertir el diagrama
no determinista en uno que lo sea vamos ha realizar los siguientes pasos:
PROPIEDADES DE LOS
LENGUAJES ACEPTADOS POR UN AUTÓMATA FINITO
Sea å un alfabeto. El conjunto
de los lenguajes regulares sobre å se define recursivamente
como sigue:
1. 1. Æ es un lenguaje regular
2. 2. }Æ{ es un lenguaje regular
3. 3. Para todo a Î å, {a} es un lenguaje regular
4. 4. Si A y B son lenguajes
regulares, entonces AÈB, A · B y A* son lenguajes regulares
5. 5. Ningún otro lenguaje sobre
å
es regular
EQUIVALENCIAS DE AFND Y AFD
Si tratamos de definir un Autómata Finito no Deterministico,
tenemos que gran parte de la definición se puede obtener a partir de la de AFD. La única diferencia que existe se encuentra en las reglas de transición.
Existe una equivalencia en entre los AFD y AFND, de forma que un autómata M es
equivalente a un autómata M’ si L(M) = L (M’).
·
·
Ya que una
función es un caso especial de relación (es decir, las funciones son relaciones
que poseen requerimientos adicionales), las funciones de los AFD se consideran
como relaciones en los AFND
·
·
En
consecuencia, todo AFD es un AFND
·
·
La colección
de lenguajes aceptados por los AFND incluye a todos los lenguajes aceptados por
los AFD
·
·
Por lo tanto,
los AFND no son más potentes que los AFD con respecto a los lenguajes que
aceptan.
·
·
Debe ser
cerrado con respecto a las operaciones de unión concatenación, cerradura de
estrella y complemento.“Un conjunto C es cerrado con respecto a la operación Å si
x, y є C ® (x
Å
y) є C
x є C ® Å x є C”
·
·
Son generados
por expresiones regulares
·
·
Son formas de
trabajo para análisis léxico
Para cada AFND, existe un AFD que acepta el mismo lenguaje.
Dado el autómata finito no determinístico MND = <END,
A, dND, e0ND, FND>,
se define el autómata finito determinístico correspondiente MD=
<ED, A, dD, e0D, FD> como sigue:
- ED = P(END) (conjunto
potencia de END).
Cada elemento de ED se representa como
[e1, e2, ..., ei] donde e1,
e2, ..., ei están en END. Se debe notar que [e1,
e2, ..., ei] es un único estado de MD que
corresponde a un conjunto de estados de MND.
- A: alfabeto
- dD: ED x A ® ED,
se define como
dD([e1, e2, ..., ei], a) = [el,
em, ..., ek]
sii
dND({e1, e2, ..., ei}, a) = dG ({e1, e2, ..., ei}, a) = {el,
em, ..., ek},
donde dG se define como dG (C, a) = È d (p, a) y dG (Æ, a) = Æ (C: conj. de estados)
p Î C
Es decir que dD aplicada a un elemento [e1, e2,
..., ei] de ED se calcula aplicando dND
a cada estado de END representado por [e1,
e2, ..., ei].
- e0D = [e0ND]
- FD: conjunto de todos los estados de ED que
contienen al menos un estado final de MND.
Ejemplo 5: Construcción del autómata finito
determinístico correspondiente al autómata finito no determinístico del ejemplo
4.
El AFD M4D correspondiente al AFND M4ND se define
como
M4D = < E4D, {0, 1}, d4D, [e0], F4D>
La función de transición d4D
se calcula como:
|
d4D |
0 |
1 |
|
[e0] |
[e0, e3] |
[e0, e1] |
|
[e0, e3] |
[e0, e3, e4] |
[e0, e1] |
|
[e0, e1] |
[e0, e3] |
[e0, e1, e2] |
|
[e0, e3, e4] |
[e0, e3, e4] |
[e0, e1, e4] |
|
[e0, e1, e2] |
[e0, e2, e3] |
[e0, e1, e2] |
|
[e0, e1, e4] |
[e0, e3, e4] |
[e0, e1, e2, e4] |
|
[e0, e2, e3] |
[e0, e2, e3, e4] |
[e0, e1, e2] |
|
[e0, e1, e2, e4] |
[e0, e2, e3, e4] |
[e0, e1, e2, e4] |
|
[e0, e2, e3, e4] |
[e0, e2, e3, e4] |
[e0, e1, e2, e4] |
Como d4ND(e0, 0) = {e0, e3},
entonces d4D([e0], 0) = [e0, e3].
Como d4ND({e0, e3}, 0)= dG({e0, e3}, 0)=d4ND(e0, 0) È d4ND(e3, 0)={e0, e3}
È
{e4} = {e0, e3, e4}
entonces d4D([e0, e3], 0) =
[e0, e3, e4].
De la misma forma se calcula d4D
para el resto de los estados.
Se debe notar que se ha calculado d4D para únicamente aquellos estados alcanzables desde el estado inicial y
a partir de los cuales se puede alcanzar un estado final. Por lo tanto, el conjunto de estados E4D es
E4D = {[e0], [e0, e3], [e0,
e1], [e0, e3, e4], [e0,
e1, e2], [e0, e1, e4],
[e0, e2, e3], [e0, e1, e2,
e4], [e0, e2, e3, e4].}
El conjunto de estados finales F4D está formado por aquellos
estados de E4D que contienen al menos un estado final de M4ND.
Entonces
F4D = {[e0, e3, e4], [e0,
e1, e2], [e0, e1, e4],
[e0, e2, e3], [e0, e1, e2,
e4], [e0, e2, e3, e4]}
Renombrando los estados correspondientes al AFD:
[e0] ® q0
[e0, e3] ® q1
[e0, e1] ® q2
[e0, e3, e4]
® q3
[e0, e1, e2] ® q4
[e0, e1, e4]
® q5
[e0, e2, e3]
® q6
[e0, e1, e2,
e4] ® q7
[e0, e2, e3,
e4] ® q8
la función de transición d4D se puede rescribir como:
|
d4D |
0 |
1 |
|
q0 |
q1 |
q2 |
|
q1 |
q3 |
q2 |
|
q2 |
q1 |
q4 |
|
q3 |
q3 |
q5 |
|
q4 |
q6 |
q4 |
|
q5 |
q3 |
q7 |
|
q6 |
q8 |
q4 |
|
q7 |
q8 |
q7 |
|
q8 |
q8 |
q7 |
Entonces M4D = <{q0, q1, q2,
q3, q4, q5, q6, q7, q8},
{0, 1}, d4D, q0, {q3, q4,
q5, q6, q7, q8}>
El diagrama de transición de estados correspondiente a este autómata es:
+ Estado 1.- Con la etiqueta a no
hay transición en el original, por lo tanto el arco se dibuja hacia el estado
vacío con la etiqueta b salen dos arcos, uno hacia el estado 2 y otro al estado
3, por lo tanto el arco se dibuja al estado 2-3
+ Estado 2.- Con la etiqueta b no
hay transición en el original, por lo tanto el arco se dibuja hacia el estado
vacío; con la etiqueta a salen dos arcos, uno hacia el estado 1 y otro al
estado 3, por lo tanto el arco se dibuja al estado 1-3.
+ Estado 3.- Con ninguna de las dos etiquetas hay transición en el
original, por lo tanto se dibujan sendos arcos hacia el estado vacío.
+ Estado 1-2.- Con la etiqueta a hay
transición desde el estado 2 original al 1 y 3 original, por lo tanto el arco
se dibuja hacia el estado 1-3; con la etiqueta b salen dos arcos desde el
estado 1 original, uno hacia el estado 2 y otro al estado 3, por lo tanto el
arco se dibuja al estado 2-3.
+ Estado 1-3.- Con la etiqueta a no hay transición desde ninguno de los
dos estados originales, por lo tanto el arco se dibuja hacia el estado vacío;
con la etiqueta b salen dos arcos desde el estado 1 original, uno hacia el
estado 2 y otro al estado 3, por lo tanto el arco se dibuja al estado 2-3.
+ Estado 2-3.- Con la etiqueta a hay
transición desde el estado 2 original al 1 y 3 original, por lo tanto el arco
se dibuja hacia el estado 1-3; con la etiqueta b no sale ningún arco en ninguno
de los dos estados originales, por lo tanto el arco se dibuja al estado vacío.
+ Estado 1-2-3.- Con la etiqueta a hay transición desde el estado 2
original al 1 y 3 original, por lo tanto el arco se dibuja hacia el estado 1-3;
con la etiqueta b salen dos arcos desde el estado 1 original, uno hacia el
estado 2 y otro al estado 3, por lo tanto el arco se dibuja al estado 2-3.