PDF de programación - Autómatas Finitos

Autómatas Finitos

Escuela Técnica Superior de Ingeniería de Telecomunicación

Universidad Rey Juan Carlos

gsyc-profes (arroba) gsyc.urjc.es

Febrero de 2018

GSyC - 2018

Autómatas Finitos

1

c2018 GSyC
Algunos derechos reservados.
Este trabajo se distribuye bajo la licencia
Creative Commons Attribution Share-Alike 4.0

GSyC - 2018

Autómatas Finitos

2

Contenidos

1 Definición

2 Ejemplo

GSyC - 2018

Autómatas Finitos

3

Automata finito

Definición

Un autómata finito, también llamado máquina de estados finita es
un modelo (matemático y/o computacional) con las siguientes
características

Acepta una secuencia de símbolos de un lenguaje

Devuelve un valor

Su funcionamiento se basa en una seria de funciones de
transición, a partir de la entrada va pasando por una serie de
estados predefinidos, hasta llegar (o no) a un estado final

Las máquinas de estados tienen muchas aplicaciones, por ejemplo
para definir el comportamiento de sistemas electrónicos. Aquí los
vemos porque son útiles en muchos algoritmos.

GSyC - 2018

Autómatas Finitos

4

Representación gráfica

Definición

Típicamente un autómata se representa mediante un grafo dirigido
al que se llama diagrama de transición de estados, donde:

Cada nodo es un estado

Las transiciones entre estados se representan con flechas

El estado inicial tiene una flecha que no tiene origen

Los estados finales se representan con un doble círculo

Cada arco se rotula con el símbolo que provoca esa transición

GSyC - 2018

Autómatas Finitos

5

Ejemplo

Ejemplo

Vamos a representar el comportamiento de un lector de DVD
Tiene los botones

pp (play/pause)

s (stop)

oc (open/close)

GSyC - 2018

Autómatas Finitos

6

Ejemplo

Definición informal del sistema en modo texto:

Si el caddy está dentro del lector, el disco está parado y
pulsamos oc, el caddy sale

Si el caddy está fuera y pulsamos oc, el caddy entra en el
lector

Si el caddy está fuera y pulsamos pp, el caddy entra en el
lector y el disco se reproduce

Si el caddy está dentro, el disco está parado y pulsamos pp, el
disco se reproduce

Si el caddy está dentro, el disco está en reproducción y
pulsamos pp, el disco se pone en modo pausa

Si el caddy está dentro, el disco está en marcha y pulsamos s,
el disco se para

GSyC - 2018

Autómatas Finitos

7

Ejemplo

Figura: Representación simplificada de un lector de DVD

GSyC - 2018

Autómatas Finitos

8

Limitaciones del ejemplo

Ejemplo

Obsérvese que un sistema real tendría que ser más complejo, este
no tiene en cuenta

Lo que suceda mientras el caddy se abre y cierra

Que el caddy no tenga disco o no sea legible

Lo que suceda mientras el disco se pone en marcha o se
detenga

etc

GSyC - 2018

Autómatas Finitos

9