Deterministic Finite Automata

Formalmente se define como una quintupla, (S, Σ, T, s, A), que consiste en:
  • Un conjunto finito de estados (S)
  • Un conjunto finito llamado alfabeto (Σ)
  • Una función llamada "transición" (T : S × Σ → S)
  • Un estado perteneciente a S llamdo estado inicial (s ∈ S).
  • Un conjunto de estados terminales o de aceptación A.
Una DFA se puede considerar como un aceptador de un lenguaje, el lenguaje del automata es simplemente el conjunto de cadenas aceptadas por su computación. Un DFA sólo puede leer la cadena de entrada sin influir en ella, se puede ver como si se tuviera una cinta donde unicamente se puede recorrer una vez al ser leida y posteriormente no tendra efecto en el cálculo.

En cualquier punto de la computación, el resultado depende unicamente del estado actual y de la entrada sin procesar, a esta combinación se le llama configuración de la maquina y se representa por el par ordenado [qi, w], donde qi es el estado actual y w elemento del todas las combinaciones del alfabeto(Σ*) es la entrada sin procesar. la función de transición es la que transforma la configuración de manera continua, hasta llegar a una transición inexistente o un estado final.


para el automata siguiente:

M: La quintupla se define de la siguiente manera,
Q={q0, q1}
Σ={A, B}
F={q1}

T(q0, A)=q1
T(q0, B)=q0
T(q1, A)=q1
T(q0, B)=q0




Este dibujo fue hecho en JFLAP, un applet de Java que usted puede descargar en www.jflap.org




En el siguiente ejemplo tenemos el automata que acepta la cadenas pertenecientes al lenguaje conformado por el alfabeto Σ={A,B,C,D,E} y que termine por ABC:
A veces se pueden llegar a tener estados sin utilidad dentro de un automata, existe un método para minimizar el DFA de tal forma que sólo contenga los estados necesarios. en el siguiente vínculo encotrara la explicación de ello, DFA minimization.