Automatas
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
1
Autómatas
Introducción
Representación
AF determinista
y lenguajes
funcionamiento
δ - ampliada
AF no
determinista
funcionamiento
δ - ampliada
no determinismo
Lenguajes
regulares
Aplicaciones
Otras máquinas
Redes de Petri
ε - movimientos
Otros autómatas
Fundamentos de Informática I. ITI Sistemas -(C) César Llamas, UVA, 2004
2
1
Autómatas
Cualquier dispositivo autónomo
Nos interesan autómatas sobre
información.
1. Leen un símbolo.
2. Producen un símbolo.
3. Vuelta al paso 1.
Se asientan en la noción de estado
Adoptan una forma procedural, más que
declarativa.
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
3
Máquina combinacional
entradaFunción
salida
salida(t)
Sólo depende
de la entrada
actual
f(entrada)
entrada(t)
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
4
2
Máquina secuencial
entrada
salida
función
historia
Φ(entrada,historia)
salida(t)
entrada(t)
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
5
Noción de estado
entrada(t)
salida(t)
…
…
estado(t)
“configuración
estado(t+1)
instantánea de un sistema”
• El sistema presenta en cada momento uno de
un conjunto de estados.
La
decisión sobre el conjunto de estados
de un sistema es puramente arbitraria.
• Ejemplo del sistema de la ventana.
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
6
3
Autómatas y Lenguajes
Tipos en términos de un lenguaje L:
• ReconocedoresPermiten especificar
lenguajes (L)
L
si
A
entrada
no
• Generadores
L’
on
A
salida
off
• Traductores
L
L’
A
entrada
salida
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
7
Sistemas de transiciones etiquetadas
Grafos
dirigidos
alfabeto de símbolos de transición (E)+
alfabeto de símbolos de nodos (Q) +
Relación {(q, e, q’)}, donde
• q, q’ ∈ Q
e1
•e∈E
e3q1
e2
q5
e2
q2
e1
q3
q4
…
…
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
8
4
Representación de autómatas
E,
alfabeto de símbolos de entrada
S, alfabeto de símbolos de salida
Q, alfabeto de símbolos de estado
f, función de evolución
g, función de salida
Si
Q es finito tenemos un AF.
Si f y g son verdaderas funciones,
tenemos un AFD.Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
9
Autómatas y tiempo
e
s
A
e
s
+ tiempo
e
e
e
A
s
s
c
reloj
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
10
5
Ejemplo de autómata (1)
a/1
q3
a/0
b/0
b/0
q1
q2
a/0
b/1
et
qt f( ) g( )
a
q1 q1
0
b
q1 q2
1
a
q2 q3
0
b
q2 q2
0
a
q3 q3
1
b
q3 q1
0
Fundamentos deInformática I. ITI Sistemas - (C) César Llamas, UVA, 2004
Ejemplo de autómata (1)
a/0
b/0
q1
a/0
q3
c/0
b/1
q4
a/1
q2
b/0
c/0
c/0
a/0,
b/0,
c/0
et
a
b
c
a
b
c
a
b
c
a
b
b
qt
q1
q1
q1
q2
q2
q2
q3
q3
q3
q4
q4
q4
11
f( ) g( )
q4 0
q3 0
q4 0
q3 1
q2 0
q4 0
q3 0
q2 1
q4 0
q4 0
q4 0
q4 0
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
12
6
Autómata finitodeterminista
ejecución
s: variable de estado (actual)
e: variable de símbolo de entrada (actual)
o: variable de símbolo de salida (actual)
s Å estado inicial
Mientras haya símbolos de entrada
1. e Å lee_símbolo();
2. [s, o] Å [f(e,s), g(e,s)];
3. emite_símbolo(o);
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
13
Representación de Mealy
et qt f( ) g( )
qiek/sm
qj
e k qi
qj
sm
f: E × Q → Q
g: E × Q → S
Fundamentos de Informática I. ITI Sistemas - (C) César Llamas, UVA, 2004
14
7
Operación del autómata de Mealy
a/0
q3
b/0
c/0
b/1
q1
q4
a/1
a/0
q2
a/0,
b/0,
c/0
c/0
b/0
c/0
Variables:
e: entrada
s: estado
s ← q1; // define el estado inicial
mientras (e Å lee_entrada()) {
emite( g(e, s) );
s Å f(e, s);
}
Fundamentos de...
Regístrate para leer el documento completo.