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 } - '=
{} (mismo estado inicial)
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. Æ es un
lenguaje regular
2. }Æ{
es un lenguaje regular
3. Para
todo a Î
å, {a} es un
lenguaje regular
4. Si
A y B son lenguajes regulares, entonces AÈB, A · B y A* son lenguajes regulares
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:
-
es la función de S' x a S'; Para cada símbolo del alfabeto y
estado s' de S', (s',x) es el estado de S' compuesto por los
estados de S a los que es posible llegar 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.
