Autómatas Finitos Deterministas (AFD)

Consulta sobre Autómatas Finitos Deterministas

1. Raúl Gómez
[email protected]

Universidad nacional de Loja

Área de la energía las industrias y los recursos naturales no renovables.
Ingeniería en Sistemas


“Autómatas y Lenguajes Formales”


Consulta sobre:
“Autómatas Finitos Deterministas (AFD)”


Nombre:
Raúl Gómez A.
Docente:
Ing. Mario Palma
Fecha:
09/10/2014


Loja-Ecuador
2014

2. Raúl Gómez
[email protected]

Autómata Finito Deterministas
Definición Autómata Finito: Se define como un conjunto de estados y un control que se
mueve de un estado a otro en respuesta a entradas externas.
Se clasifican en función del tipo de control:

Deterministas: El autómata únicamente puede estar en un estado en un momento
determinado.
No Determinista: El autómata puede estar en varios estados simultáneamente.
(Francisco Moreno Pag.4)

 EPRESENTACIÓN DE UN AFD
Tenemos dos maneras de representar un AFD
Con una tabla:
Se ponen tantas filas como estados, y tantas columnas como símbolos forman el
alfabeto. Marcamos el estado inicial con una flecha de entrada y cada uno de los estados
finales con un asterisco. En el cruce de la fila marcada con el estado q y la columna
marcada con el símbolo a del alfabeto ponemos el estado δ(q,a).

Con un diagrama:

Cada estado no final se representa con un círculo; cada estado final se
representa con un doble círculo; se señala el estado inicial con una flecha entrando, sin
etiqueta; por cada transición δ (q,a)=t se dibuja una flecha dirigida del estado de partida
q al de llegada t etiquetada a

3. Raúl Gómez
[email protected]

Estructura:
La máquina M1 del ejemplo se representa con una tabla


O bien se representa con un diagrama:

Observemos que cada una de ambas representaciones contiene toda la información del
autómata. (I.Luengo pag. 3)
EJEMPLO:
• Diseñar un AFD que reconozca palabras que contienen la cadena 001 como 0010, 1001,
11111110011111, pero no como 11, 0000, 1100, 10101.
Posibilidades:
– No hemos leído ningún símbolo. Estado q.
– Hemos leído un 0. Estado q0.
– Hemos leído 00. Estado q00.
– Hemos leído 001. Estado q001

4. Raúl Gómez
[email protected]



Bibliografía
(M Francisco ) http://www.uhu.es/francisco.moreno/talf/docs/tema4_2.pdf
(I.Luengo 2014) http://www2.dis.ulpgc.es/~mluengo/automatas/teoria/tema2.pdf