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:
- S'
= P(S) Conjunto de todos los subconjuntos de S (recordar que el conjunto
potencia se encuentra incluido el conjunto vacío, que será el estado de
captación global)
Como tenemos tres estados, el conjunto potencia P(S) , 1, 2, 3, 1-2, 1-3, 2-3, 1-2-3 }l= { - '=i
} (mismo estado inicial)i{
En nuestro caso seguirá siendo el estado 1. - F'
es la colección de subconjuntos de S (estados de S') que contienen, por lo
menos, un estado de F (cada uno de los estados de S' dentro de los cuales
hay al menos un estado de aceptación de M).
En nuestro caso serán todos los subconjuntos que tengan el estado 3, ya que este es el único estado de aceptación del diagrama original; luego F'= { 3, 1-3, 2-3, 1-2-3 }
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:
- d es la d a S'; Para cada
símbolo del alfabeto y estado s' de S', Sfunción de S' x (s',x) es el estado de S' compuesto por
los estados de S a los que es posible dllegar desde todos
los estados s de s' siguiendo un arco con etiqueta x. Como es una función, M' es finito
determinista.
En nuestro caso, En cada estado del conjunto potencia solo va a salir un arco por cada símbolo, siendo el destino, el estado de S' que tenga todos los estados a los que fuera en el diagrama inicial: para ello:
+ vacío.- como dijimos, era el estado de captación global, por lo tanto se le dibujan tantos arcos que salen e inciden en el estado, como símbolos del alfabeto haya, con los cuales se rotulan. Además, en este estado, van a incidir todas aquellas transiciones que no existían para algún símbolo en algún estado original.
+ 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.
- Una
vez que hemos terminado todos los pasos, podremos eliminar aquellos
estados que sean superfluos al diagrama que acabamos de obtener.
En nuestro caso particular podemos eliminar los estados 2, 3, 1-2 y 1-2-3, quedando el definitivo autómata finito determinista