Autómata finito determinista

El autómata finito se puede clasificar en dos tipos:

• Autómata finito determinista (DFA)
• Autómata finito no determinista (NDFA / NFA)

Autómata finito determinista (DFA)

En DFA, para cada símbolo de entrada, se puede determinar el estado al que se moverá la máquina. Por lo tanto, se llamaDeterministic Automaton. Como tiene un número finito de estados, la máquina se llamaDeterministic Finite Machine o Deterministic Finite Automaton.

Definición formal de un DFA

Un DFA puede estar representado por una tupla de 5 (Q, ∑, δ, q ₀ , F) donde -

• Q es un conjunto finito de estados.

• ∑ es un conjunto finito de símbolos llamado alfabeto.

• δ es la función de transición donde δ: Q × ∑ → Q

• q₀es el estado inicial desde donde se procesa cualquier entrada (q ₀ ∈ Q).

• F es un conjunto de estados finales de Q (F ⊆ Q).

Representación gráfica de un DFA

Un DFA está representado por dígrafos llamados state diagram.

• Los vértices representan los estados.
• Los arcos etiquetados con un alfabeto de entrada muestran las transiciones.
• El estado inicial se denota por un solo arco entrante vacío.
• El estado final está indicado por círculos dobles.

Ejemplo

Sea un autómata finito determinista →

• Q = {a, b, c},
• ∑ = {0, 1},
• q ₀ = {a},
• F = {c} y

Función de transición δ como se muestra en la siguiente tabla -

Estado actual	Siguiente estado para la entrada 0	Siguiente estado para la entrada 1
a	una	segundo
b	C	una
c	segundo	C

Su representación gráfica sería la siguiente: