U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATA FINITO (AF):
El Autómata Finito es la máquina más restrictiva de todas y desde luego que se puede definir como un caso particular de una MT. También podemos verla como un AP sin pila. Obviamente que al sacarle la pila lo único que queda es la cinta finita de entrada. Este modelo matemático abstracto representa la
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
cinta finita de entrada. Este modelo matemático abstracto representa la solución del problema de aceptación de lenguajes de tipo 3 o LR. Para su mejor comprensión lo representaremos con el siguiente esquema:
e1 e2••• ••• en-1 en
Cinta Finita Entrada
Control
Cabezal de Lectura
0 12
X
3.. .E
stad
os
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATA FINITO (AF):
Al comienzo se escribe en la cinta de entrada la palabra que se desea analizar (ei ), la misma termina con un símbolo de fin de cadena que por simplicidad no consideraremos en forma explícita y un cabezal de lectura se encuentra sobre la posición del primer símbolo de dicha palabra.
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
posición del primer símbolo de dicha palabra. Esta descripción corresponde al estado inicialy desde aquí el modelo comienza a funcionar del siguiente modo:1) LEE un símbolo de la cinta de entrada y mueve el cabezal a la derecha.2) De acuerdo al ESTADO ACTUALy al símbolo leído, transiciona a un NUEVO
ESTADO (que puede ser el mismo).3) Repite 1) y 2) hasta que lee totalmente la palabra, en este caso si se encuentra en
alguno de los llamados ESTADOS FINALESse dice que la palabra escrita inicialmente es ACEPTADAy en caso contrario es RECHAZADA; o hasta que se llega a un estado en el que no está definida una transición, entonces se dice que el AF se BLOQUEA y la secuencia de entrada es RECHAZADA.
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATA FINITO (AF):
Definición formal de un Autómata Finito:
AF = ⟨⟨⟨⟨ Q , Σ , q0 , F , f ⟩⟩⟩⟩
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
0
Q : Conjunto finito y no vacío de estados.Σ : Alfabeto de símbolos de entrada.q0 : Estado inicial (perteneciente a Q).F : Conjunto de estados finales (incluido en Q).f : Función de control o transición, que se define como:
f : Q x ΣΣΣΣ ⇒⇒⇒⇒ Q En este caso F esta en el dominio, es decir que los estados finales no son de parada y el final de cadena está implícito en el funcionamiento del AF.
U.T.N. – F.R.T. S. y S. de los L.
En el caso de los AF y en correspondencia con el algoritmo constructivo de comprobación de pertenencia para LDC, que por
jerarquía de Chomsky vale para LR, el lenguaje universal ΣΣΣΣ* ,
AUTÓMATA FINITO (AF):
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
jerarquía de Chomsky vale para LR, el lenguaje universal ΣΣΣΣ* , queda dividido en dos subconjuntos:
Es decir que para todo LR existe un AF que es capaz de aceptarlo y a la vez rechazar a su complemento.
ΣΣΣΣ* �Todas las palabras aceptadas por el AF.�Todas las palabras rechazadas por el AF.
U.T.N. – F.R.T. S. y S. de los L.
Representación formal de la función de transición:
Tabla de Transición
AUTÓMATA FINITO (AF):
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
Tabla de Transición
Grafo de Transición
Fq0 q’qe
q’eqEst. NuevoSímb. LeídoEst. Actual
U.T.N. – F.R.T. S. y S. de los L.
En ambos casos se representa cada pareja estímulo/ /reacción, compuesta por el par (estado actual, símbolo leído) y el (estado nuevo) respectivamente.
AUTÓMATA FINITO (AF):
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
nuevo) respectivamente.
Al igual que todos los modelos, la relación de transición puede ser deterministao no-determinista. Pero en este caso se puede demostrar que el AF es DETERMINISTA por naturaleza.
Es decir que todos los AF no-deterministas tienen un equivalente determinista.
U.T.N. – F.R.T. S. y S. de los L.
AF = ⟨⟨⟨⟨ Q , Σ , q0 , F , f ⟩⟩⟩⟩
Q = { 1, 2 }
EJEMPLO DE AF:
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
Q = { 1, 2 }
ΣΣΣΣ = { a, b }
q0 = 1 F = { 2 }
Este AF acepta el lenguaje L(AF) = { an bm / n ≥≥≥≥ 0 , m ≥ ≥ ≥ ≥ 1 } sobre el alfabeto {a, b}, que contiene todas las palabras compuestas por una secuencia de “a” seguida de otra secuencia de “b” o solamente una secuencia de “b”.
La función de control f se representa con su tabla y grafo de transición.
U.T.N. – F.R.T. S. y S. de los L.
EJEMPLO DE AF:G
RA
FO
DE
TR
AN
SIC
IÓN
a bTABLA DE
TRANSICIÓN
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
GR
AF
O D
E T
RA
NS
ICIÓ
N
1 2
a b
b
TRANSICIÓN
Est. Actual
Sím.
LeídoEst.
Nuevo
→→→→ 1 a 1
1 b 2
* 2 b 2
U.T.N. – F.R.T. S. y S. de los L.
CONFIGURACIÓN DE UN AF:
Una descripción instantánea de un AF requiere las siguientes especificaciones:
� Estado actual del AF.
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
� Estado actual del AF.� Contenido que falta leer de la cinta de entrada.
Este par constituye la CONFIGURACIÓN del AF y vamos a representar con el estado actual seguido de la secuencia de símbolos que faltan leer en la cinta de entrada: qkei...en
De igual modo que en los modelos anteriores, una sucesión de configuraciones consecutivas se llama SECUENCIA DE CONFIGURACIÓN del AF.
U.T.N. – F.R.T. S. y S. de los L.
LENGUAJE ACEPTADO POR UN AF:
Se define el lenguaje aceptado por un AF como el conjunto de palabras que partiendo de una configuración inicial, llegan a una configuración que contiene un estado final del AF y el total
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
una configuración que contiene un estado final del AF y el total de la entrada leída. Formalmente se representa como:
L(AF) = {w / w∈Σ∈Σ∈Σ∈Σ* ∧∧∧∧ q0w├─ * qF ∧∧∧∧ qF ∈∈∈∈ F }
Por otro lado, todas las palabras que partiendo de una configuración inicial llegan a un estado no final o producen el bloqueo del modelo, dice que son rechazadas por el AF.
U.T.N. – F.R.T. S. y S. de los L.
EJEMPLO DE SECUENCIA DE CONFIGURACION:
Consideremos el ejemplo de AF anterior y las palabras:
w1 = aabbb , w2 = bb , w3 = aaa , w4 = baa
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
ING. JORGE BUABUD
Las secuencias de configuración correspondientes serían:
1) 1aabbb ├─ 1abbb ├─ 1bbb ├─ 2bb├─ 2b ├─ 2 final/acepta
2) 1bb ├─ 2b ├─ 2 final/acepta
3) 1aaa ├─ 1aa├─ 1a ├─ 1 no-final/rechaza
4) 1baa ├─ 2aa bloqueo/rechaza
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
En síntesis:
� Los AF son modelos abstractos capaces de aceptar LR.
ING. JORGE BUABUD
� Un AF es un caso particular de MT con ciertas restricciones.
� Un AF es Determinista (AFD) si para cada estímulo tiene
solo una reacción posible, caso contrario es No-determinista.
� Por naturaleza estos modelos son DETERMINISTAS.
� La función de transición tiene los siguientes dominio y rango
f : Q x ΣΣΣΣ ⇒⇒⇒⇒ Q
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
AUTÓMATA CONEXO : Un AFD se dice conexo cuando todos sus estados son accesibles desde el estado inicial.
AUTÓMATA COMPLETO : Un AFD se dice completo cuando todos
ING. JORGE BUABUD
AUTÓMATA COMPLETO : Un AFD se dice completo cuando todos sus estados tienen transiciones con cada uno de los símbolos de entrada válidos.
ESTADO SUMIDERO: Un estado se llama sumidero cuando no es final y transiciona con todos los símbolos de entrada a si mismo. Es un estado de rechazo.
ESTADO GENERADOR: Un estado se llama generador cuando solo salen transiciones desde él. Solo es útil cuando es el inicial.
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
EJEMPLOS DE AFD:b 32b
b aa
ba
a bAFD1
AFD2
ING. JORGE BUABUD
1 2
4
3
5a
a
b
a
ab
Características:� Conexo� Incompleto� Estado 1 generador
1
4
7
5
b
b
ba
a b
Características:� No-conexo� Completo� Estado 5 generador � Estado 6 sumidero
6
b,a
a
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
EJEMPLOS DE AFD:
bAFD3
b
32ba
a
ab
AFD4
ING. JORGE BUABUD
1 2
4
3
5a
a
bb
a
a
Características:� Conexo� Completo� Estado 4 sumidero
b
b
a,bCaracterísticas:� Conexo� Completo� Estado 1 generador � Estado 4 sumidero
1
4
6
5
b
b,a
ba
a ba
b
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
REPRESENTACIÓN MATRICIAL :Cuando tenemos un AF completo conviene representar su función de transición con una matriz cuyas columnas representan los símbolos de
ING. JORGE BUABUD
transición con una matriz cuyas columnas representan los símbolos de entrada y sus filas los estados. AFD4 a b
→→→→1 4 2
*2 3 2
3 4 6
4 4 4
*5 4 3
*6 6 5
AFD2 a b
→→→→1 1 2
*2 7 2
3 2 7
4 3 4
*5 4 7
6 6 6
*7 6 7
AFD3 a b
→→→→1 2 1
2 3 4
3 5 1
4 4 4
*5 2 4
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
¿ CÓMO HACEMOS CONEXO A UN AF ? :
Simplemente se elimina los estados inaccesibles y todas las transiciones que salen o llegan a ellos. Hay una correspondencia entre estos estados y los
ING. JORGE BUABUD
salen o llegan a ellos. Hay una correspondencia entre estos estados y los No-terminales inútiles de una GR. Por ejemplo, el AFD2 quedaría:
AFD2 a b
→→→→1 1 2
*2 7 2
6 6 6
*7 6 7
b
1
2
7
ba
6b,a
a
ba
AFD2
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
¿ CÓMO COMPLETAMOS UN AF ? :
Si el AF tiene un estado sumidero o algún estado sin transiciones, enviamos todas las transiciones faltantes hacia ese estado. Caso contrario
ING. JORGE BUABUD
todas las transiciones faltantes hacia ese estado. Caso contrario agregamos un estado sumidero nuevo y procedemos igual.Por ejemplo, el AFD1 quedaría:
1
2
4
3
5
a a
b
b
a
ab
AFD1
6
b
aba,b
AFD1 a b→→→→1 2 6
2 3 4
3 5 3
4 6 5
*5 2 6
6 6 6
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
Ejemplos de AFD para ER sencillas:Lenguaje sobre ΣΣΣΣ={a,b,c} de secuencias de“a,b” con prefijo “a,b,c” y con sufijo “c”
Lenguaje sobre ΣΣΣΣ={a,b} de secuenciasde “a” con prefijo “ab” y sufijo “ba” :
ING. JORGE BUABUD
“a,b” con prefijo “a,b,c” y con sufijo “c”más secuencias de “a”:
ER = (a+b+c).(a+b)*.c.a*
AFD5
2 3a, b, c c
1
a, b a
4a, b, c
b, c
de “a” con prefijo “ab” y sufijo “ba” :
ER = a.b.a*.b.a
AFD6
31
2
a b a
b
a, b
4
5
6
a
b
a
a
a, b
b
LENGUAJES REGULARES Y AUTÓMATAS FINITOS
U.T.N. – F.R.T. S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
Ejemplos de AFD para ER sencillas:Lenguaje de secuencias pares y λλλλsobre ΣΣΣΣ={a, b, c}:
Lenguaje de secuencias con prefijo “a” y sufijo “b” sobre ΣΣΣΣ={a, b}:
ING. JORGE BUABUD
sobre ΣΣΣΣ={a, b, c}:
ER = ((a+b+c).(a+b+c))*
AFD7
2 31a, b, c
a, b, c
a, b, c
“a” y sufijo “b” sobre ΣΣΣΣ={a, b}:
ER = a.(a+b)*.b
AFD8
a
2 41
3
a b
b
ab
a,b
Top Related