Autômato Finito Determinístico

O autômato finito pode ser classificado em dois tipos -

• Autômato Finito Determinístico (DFA)
• Autômato Finito Não Determinístico (NDFA / NFA)

Autômato Finito Determinístico (DFA)

No DFA, para cada símbolo de entrada, pode-se determinar o estado para o qual a máquina se moverá. Por isso, é chamadoDeterministic Automaton. Por ter um número finito de estados, a máquina é chamadaDeterministic Finite Machine ou Deterministic Finite Automaton.

Definição formal de um DFA

Um DFA pode ser representado por uma 5-tupla (Q, ∑, δ, q ₀ , F) onde -

• Q é um conjunto finito de estados.

• ∑ é um conjunto finito de símbolos chamado alfabeto.

• δ é a função de transição onde δ: Q × ∑ → Q

• q₀é o estado inicial de onde qualquer entrada é processada (q ₀ ∈ Q).

• F é um conjunto de estados / estados finais de Q (F ⊆ Q).

Representação gráfica de um DFA

Um DFA é representado por dígrafos chamados state diagram.

• Os vértices representam os estados.
• Os arcos marcados com um alfabeto de entrada mostram as transições.
• O estado inicial é denotado por um único arco de entrada vazio.
• O estado final é indicado por círculos duplos.

Exemplo

Seja um autômato finito determinístico →

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

Função de transição δ conforme mostrado pela tabela a seguir -

Estado atual	Próximo estado para a entrada 0	Próximo estado para a entrada 1
a	uma	b
b	c	uma
c	b	c

Sua representação gráfica seria a seguinte -