Autómata finito determinista

¿Qué es?

Es aquel que sólo puede estar en un único estado después de leer cualquier secuencia de entradas. El término “determinista” hace referencia al hecho de que para cada entrada sólo existe uno y sólo un estado al que el autómata puede hacer la transición a partir de su estado actual.

La transición solo puede llevar a un estado ya definido

Construcción

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.

Notación

Hay disponibles dos notaciones más cómodas para describir los autómatas:

1. Un diagrama de transiciones, que es un grafo. 

2. Una tabla de transiciones, que es una ordenación tabular de la función δ, la cual especifica el conjunto de estados y el alfabeto de entrada.

Diagramas de transiciones 

Un diagrama de transiciones de un AFD A = (Q,Σ,δ,q0,F) es un grafo definido como sigue: 

a) Para cada estado de Q, existe un nodo. 

b) Para cada estado q de Q y cada símbolo de entrada a de Σ, sea δ(q,a) = p. Entonces, el diagrama de transiciones tiene un arco desde el nodo q hasta el nodo p, etiquetado como a. Si existen varios símbolos de entrada que dan lugar a transiciones desde q hasta p, entonces el diagrama de transiciones puede tener un único arco etiquetado con la lista de estos símbolos. 

c) Existe un flecha dirigida al estado inicial q0, etiquetada como Inicio. Esta flecha no tiene origen en ningún nodo. 

d) Los nodos correspondientes a los estados de aceptación (los que pertenecen a 

F) están marcados con un doble círculo. Los estados que no pertenecen a F tienen un círculo simple.

Lenguaje

Ahora podemos definir el lenguaje de un AFD A = (Q,Σ,δ,q0,F). Este lenguaje se designa por L(A) y se define como:

L(A) = {w | δ(q0,w) pertenece a F}

Es decir, el lenguaje de A es el conjunto de cadenas w que parten del estado inicial q0 y van hasta uno de los estados de aceptación. Si L es L(A) para un determinado AFD A, entonces decimos que L es un lenguaje regular.

El “lenguaje” del AFD es el conjunto de todas las cadenas que acepta

EJ.