Definición de A.F.D.

A.F.D.

Definición de autómata finito determinista

Un autómata finito determinista consta de:

1. Un conjunto finito de estados, a menudo designado como Q.

2. Un conjunto finito de símbolos de entrada, a menudo designado como Σ.

3. Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve un estado. La función de transición se designa habitualmente como δ . En nuestra representación gráfica informal del autómata, δ se ha representa mediante arcos entre los estados y las etiquetas sobre los arcos.

Si q es un estado y a es un símbolo de entrada, entonces δ (q,a) es el estado p tal que existe un arco etiquetado a que va desde q hasta p.2

 

4. Un estado inicial, uno de los estados de Q.

5. Un conjunto de estados finales o de aceptación F. El conjunto F es un subconjunto de Q.

 

A menudo haremos referencia a un autómata finito determinista mediante su acrónimo: AFD. 

La representación más sucinta de un AFD consiste en un listado de los cinco componentes anteriores. Normalmente, en las demostraciones, definiremos un AFD utilizando la notación de “quíntupla” siguiente:

 

A = (Q, Σ,δ ,q0,F)

 

donde:

 

A es el nombre del AFD

Q es su conjunto de estados

Σ son los símbolos de entrada

δ es la función de transición

q0 es el estado inicial y 

F es el conjunto de estados finales.

Fuente:Hopcroft, J. E.; Motwani, R.; Ullman, J. D.,"Introducción a la teoría de autómatas,

lenguajes y computación",PEARSON EDUCACIÓN S.A., Madrid, 2007