Automatas Finitos

2 Autómatas Finitos

2.1 AUTÓMATAS FINITOS DETERMINISTAS (AFD).

2.1.1 DEFINICIÓN DE AFD.

Un autómata finito determinista es una quíntupla que denotaremos de manera genérica

por M=(Q,Σ,q0,δ,F) donde:

Q es un conjunto finito cuyos elementos llamaremos estados.

Σ es un alfabeto que llamamos alfabeto de entrada.

q0∈Q es un estado señalado que llamamos estado inicial.

F es un subconjunto de Q no vacío, cuyos elementos llamamos estados finales.

δ es una aplicación de Q×Σ→Q , que llamamos función de transición.

La función de transición es la verdadera clave de la máquina. Obsérvese que es una

aplicación, así cada pareja posible formada por un estado y un símbolo del alfabeto debe

tener una imagen y sólo una, es decir δ(q,a)∈Q, cualquiera que sean q∈Q y a∈Σ.

Ejemplos:

2. Autómatas Finitos 2.1 Autómatas Finitos Deterministas (AFD)

© Inmaculada Luengo

20

Sea M1 = (Q, Σ, δ, q0,F) donde Q={p,q,r}, Σ={a,b}, Sea p el estado inicial, F={r} y δ

definida como sigue:

δ(p,a)=q δ(p,b)=r

δ(q,a)=p δ(q,b)=q

δ(r,a)=r δ(r,b)=r

Tabla 2.1. Función de transición de M1.

Según nuestra definición M1 es un AFD.

Para visualizarlo de alguna forma imaginemos una especie de circuito electrico con

tantas bombillas como estados, las correspondientes a los estados finales de color verde,

las demás amarillas. Sobre una cinta de entrada escribimos una palabra con símbolos del

alfabeto de entrada. Al poner a funcionar la máquina se enciende la bombilla

correspondiente al estado inicial. A partir de ese momento se procesa el símbolo actual

en la cinta de entrada transitando al estado definido en cada momento por la función de

transición hasta que la palabra de la entrada haya sido leido completa.

Si la palabra a procesar fuese aabbab, se enciende el estado p inicial y a continuación

qprrrr. El estado que queda encendido es r que es final. Si la palabra a procesar fuese

abbb la secuencia de estados sería pqqqq.

2.1.2 REPRESENTACIÓN DE UN AFD.

Tenemos dos maneras de representar un AFD

...