Automatas

Autómatas

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...