• A máquina de estados finitos é usada para reconhecer padrões.
• A máquina de autômatos finitos pega a sequência de símbolos como entrada e muda seu estado de acordo. Na entrada, quando um símbolo desejado é encontrado, ocorre a transição.
• Durante a transição, o autômato pode passar para o próximo estado ou permanecer no mesmo estado.
• FA tem dois estados: estado de aceitação ou estado de rejeição. Quando a string de entrada for processada com sucesso e o autômato atingir seu estado final, ele aceitará.

Um autômato finito consiste no seguinte:

Q: conjunto finito de estados
∑: conjunto finito de símbolos de entrada
q0: estado inicial
F: estado final
d: Função de transição

A função de transição pode ser definida como

 δ: Q x ∑ →Q 

FA é caracterizada de duas maneiras:

1. DFA (autômatos finitos)
2. NDFA (autômatos finitos não determinísticos)

AFD

DFA significa Autômato Finito Determinístico. Determinístico refere-se à singularidade da computação. No DFA, o caractere de entrada vai para apenas um estado. O DFA não aceita a movimentação nula, o que significa que o DFA não pode alterar o estado sem qualquer caractere de entrada.

DFA tem cinco tuplas {Q, ∑, q0, F, δ}

Exemplo

Veja um exemplo de autômato finito determinístico:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 

NDFA

NDFA referem-se aos Autômatos Finitos Não Determinísticos. É usado para transitar qualquer número de estados para uma entrada específica. O NDFA aceita o movimento NULL, o que significa que pode mudar de estado sem ler os símbolos.

O NDFA também tem cinco estados iguais ao DFA. Mas o NDFA tem uma função de transição diferente.

A função de transição do NDFA pode ser definida como:

Exemplo

Veja um exemplo de autômatos finitos não determinísticos:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3}