Autômatos Finitos Determinísticos (AFD)

O que é um AFD

Um autômato finito determinístico (AFD) é uma máquina com memória finita — um conjunto finito de estados — que lê uma cadeia (sequência finita de símbolos de um alfabeto finito $\Sigma$) da esquerda para a direita, um símbolo por vez, e decide aceitar ou rejeitar.

Determinístico significa: em cada estado, para cada símbolo do alfabeto, há exatamente uma transição. Não há escolha e não há transição vazia ($\varepsilon$).

O propósito é reconhecer linguagens formais: conjuntos de cadeias extraídas de um alfabeto finito $\Sigma$. A linguagem do AFD é o conjunto das cadeias que, após a leitura completa, deixam a máquina num estado final.

Definição formal

A seção anterior já nomeou os estados, o alfabeto, a transição única por símbolo, o começo da leitura e a aceitação no fim da cadeia:

Um AFD é a quíntupla

onde:

• $Q$ é um conjunto finito de estados;
• $\Sigma$ é o alfabeto finito de entrada;
• $\delta: Q \times \Sigma \to Q$ é a função de transição total: em conjuntos finitos, as desigualdades de tamanho são obrigatórias — o domínio $Q\times\Sigma$ tem $|Q|\cdot|\Sigma|$ pares, e cada par $(q, a)$, com $q \in Q$ e $a \in \Sigma$, corresponde um sucessor $\delta(q, a) \in Q$;
• $q_0 \in Q$ é o estado inicial, onde a leitura começa;
• $F \subseteq Q$ é o conjunto de estados finais (aceitação).

Por que $\delta$ é total? Sem isso, algum par $(q, a)$ não teria sucessor e a leitura pararia sem estado definido no meio da cadeia.

Completar $\delta$ — por exemplo com um poço que rejeita e não sai mais — garante que toda $w \in \Sigma^*$ (toda cadeia finita sobre $\Sigma$, inclusive a vazia) tem um único percurso. Escreve-se $\hat{\delta}(q_0, w)$ para o estado depois de ler toda a cadeia $w$ a partir de $q_0$. A linguagem fica bem definida:

São as palavras cujo percurso termina em $F$. O estado depois do último símbolo define aceitação; estados finais visitados no meio do caminho não contam.

O processamento começa em $q_0$ e consome os símbolos na ordem. Não há como “voltar” na fita nem pular um símbolo: cada $a_i$ aplica $\delta$ exatamente uma vez.

Exemplo

Alfabeto $\Sigma = \{0,1\}$. Dois estados: $q_{\mathrm{par}}$ (o número de zeros lidos até agora é par) e $q_{\mathrm{ímpar}}$.

Quíntupla: $Q = \{q_{\mathrm{par}}, q_{\mathrm{ímpar}}\}$, inicial $q_{\mathrm{par}}$, finais $F = \{q_{\mathrm{par}}\}$, e

Um $0$ inverte a paridade dos zeros já lidos, então a tabela aponta para o outro estado; um $1$ não inverte, então a tabela devolve o mesmo estado. A cadeia $1010$ tem dois zeros. Começa em $q_{\mathrm{par}}$ (nenhum zero). O $1$ permanece em $q_{\mathrm{par}}$; o primeiro $0$ vai a $q_{\mathrm{ímpar}}$ (um zero); o $1$ permanece; o último $0$ volta a $q_{\mathrm{par}}$ (dois zeros):

Termina em $F$: aceita. A cadeia $10$ tem um zero e termina em $q_{\mathrm{ímpar}}$: rejeita.

A vazia $\varepsilon$ fica em $q_{\mathrm{par}}$ e é aceita — zero zeros é par.

O estado guarda só a paridade dos zeros — um bit de memória. Isso é o que “estado finito” permite guardar. Dois estados não distinguem $00$ de $0000$; a linguagem só pergunta a paridade, e para isso basta.

Extensão da transição

A função $\delta$ consome um símbolo. Para uma cadeia $w = a_1 a_2 \cdots a_n$, estende-se a $\hat{\delta}: Q \times \Sigma^* \to Q$:

Começando em $q_0$, o estado após $w$ é $\hat{\delta}(q_0, w)$. A mesma leitura escreve $q_i = \delta(q_{i-1}, a_i)$ para $1 \leq i \leq n$. O AFD aceita $w$ se e somente se $q_n \in F$.

A cadeia vazia $\varepsilon$ é aceita exatamente quando $q_0 \in F$, porque $\hat{\delta}(q_0, \varepsilon) = q_0$. Por isso o AFD da paridade aceita $\varepsilon$: o inicial é final.

A extensão é uma indução no comprimento. Os dois ingredientes são obrigatórios por razões distintas: $\hat{\delta}(q,\varepsilon)=q$ porque a cadeia vazia não traz símbolo; $\hat{\delta}(q,xa)=\delta(\hat{\delta}(q,x),a)$ porque o próximo símbolo $a$ só se aplica depois de conhecido o estado no prefixo $x$. Cada símbolo entra na definição recursiva, na ordem.

O determinismo entra aqui: de cada estado, $\delta(\,\cdot\,, a)$ devolve um único sucessor, então $\hat{\delta}(q_0, w)$ é um único estado — nunca um conjunto.

Um grafo dirigido tem arestas orientadas: cada arco é um par ordenado, de um estado $q$ para o sucessor $\delta(q,a)$, com o rótulo $a\in\Sigma$. O inicial se destaca; cada final leva círculo duplo. O determinismo aparece no desenho: de cada vértice sai uma aresta por símbolo.

Se faltasse alguma aresta, $\delta$ não seria total: complete com um poço $q_{\bot} \notin F$ do qual todo símbolo volta a $q_{\bot}$. Sem o poço, cadeias que usam um par estado–símbolo sem aresta no grafo não teriam $\hat{\delta}$ definido.

Cadeias que terminam em $1$

Seja $L = \{ w \in \{0,1\}^* \mid w \text{ termina em } 1 \}$. O AFD só precisa lembrar o último símbolo lido.