Autómatos finitos

Para saber se uma palavra termina em $ab$, chega guardar o sufixo útil do prefixo lido. Depois de $baa$, interessa o último $a$; depois de $baab$, interessa $ab$. Um autómato finito guarda esse resumo num estado.

A expressão $(a+b)^*ab$ descreve a mesma condição por blocos. Aqui vamos construir a máquina que a verifica letra a letra.

DFA: definição e leitura

Um autómato finito determinístico, DFA, é $M=(Q,\Sigma,\delta,q_0,F)$:

• $Q$ é um conjunto finito e não vazio de estados;
• $\Sigma$ é o alfabeto de entrada;
• $\delta:Q\times\Sigma\to Q$ é a função de transição;
• $q_0\in Q$ é o estado inicial;
• $F\subseteq Q$ é o conjunto de estados finais, ou de aceitação.

Nesta definição, $\delta$ é total: existe exatamente um destino para cada par estado/símbolo. Um desenho incompleto abrevia transições para um estado poço, do qual nunca se sai. Uma transição ausente não significa que a máquina ignore a letra.

No diagrama, uma seta sem origem marca o início e um círculo duplo marca um estado final. Entrar num estado final a meio da palavra não termina a leitura, porque a aceitação depende do estado depois de consumir toda a entrada.

Construir estados com significado

Vamos reconhecer $L=\{w\in\{a,b\}^*\mid w\text{ termina em }ab\}$. Escolhe:

• $q_0$: não há um sufixo útil, incluindo o início;
• $q_1$: o prefixo lido termina em $a$;
• $q_2$: o prefixo lido termina em $ab$.

Estado	Lê $a$	Lê $b$	Final?
$q_0$ inicial	$q_1$	$q_0$	Não
$q_1$	$q_1$	$q_2$	Não
$q_2$	$q_1$	$q_0$	Sim

Em $q_1$, outro $a$ mantém o sufixo útil $a$. Em $q_2$, um $b$ transforma o sufixo $ab$ em $abb$, que já não termina em $ab$ nem em $a$.

A ligação entre $q_1$ e $q_2$ lê $b$ no sentido descendente e $a$ no ascendente. A palavra $baab$ segue por isso $q_0,q_0,q_1,q_1,q_2$ e é aceite, enquanto $aba$ passa em $q_2$ mas termina em $q_1$ e é rejeitada; $\varepsilon$ termina no estado inicial, que não é final.

Construir e testar o DFA

Edita os estados, o estado inicial, os finais e as transições no laboratório. Cada par estado/símbolo precisa de exatamente uma transição: uma tabela incompleta é um erro de construção, não uma rejeição da palavra. Experimenta aba passo a passo para observar a passagem por um estado final antes do fim da entrada.

Em Resolver exercício, corrige a máquina e verifica o comportamento; os exemplos de teste ajudam a localizar erros, enquanto a comparação completa explora todos os pares de estados alcançáveis com a máquina de referência e mostra uma palavra que revela qualquer diferença. Renomear estados ou acrescentar estados inacessíveis não altera a linguagem reconhecida.

De onde sai cada transição de recuperação

Cada transição responde à mesma pergunta: se o prefixo lido até agora está resumido no estado $p$ e chega a letra $a$, qual é o resumo do prefixo maior? A resposta é sempre o sufixo mais comprido do prefixo maior que ainda seja útil, isto é, $a$ ou $ab$.

Estás em	Chega	Prefixo maior termina em	Vais para
$q_0$	$b$	sem sufixo útil	$q_0$
$q_1$	$a$	$aa$, cujo sufixo útil é $a$	$q_1$
$q_2$	$a$	$aba$, cujo sufixo útil é $a$	$q_1$
$q_2$	$b$	$abb$, sem sufixo útil	$q_0$

Verifica com palavras concretas: $aab$ segue $q_0,q_1,q_1,q_2$ e aceita; $abb$ segue $q_0,q_1,q_2,q_0$ e rejeita; $abab$ visita $q_2$ a meio mas termina em $q_2$ e aceita.

Transição estendida

$\delta$ lê um símbolo. Para ler uma palavra, definimos $\widehat\delta:Q\times\Sigma^*\to Q$:

$$\widehat\delta(q,\varepsilon)=q,\qquad \widehat\delta(q,xa)=\delta(\widehat\delta(q,x),a).$$

Assim, $L(M)=\{w\in\Sigma^*\mid\widehat\delta(q_0,w)\in F\}$. Por exemplo,

$$\widehat\delta(q_0,ab)=\delta(\delta(q_0,a),b)=\delta(q_1,b)=q_2.$$

Ver por que podemos dividir a entrada em qualquer posição

Para quaisquer $x,y$, vale

$$\widehat\delta(q,xy)=\widehat\delta(\widehat\delta(q,x),y),$$

ou seja, podemos continuar a leitura a partir do estado deixado pelo prefixo. Prova por indução em $|y|$: a base $y=\varepsilon$ dá $\widehat\delta(q,x)$ de ambos os lados. Se vale para $y=z$, então, para $y=za$:

$$\begin{aligned} \widehat\delta(q,xza) &=\delta(\widehat\delta(q,xz),a)\\ &=\delta(\widehat\delta(\widehat\delta(q,x),z),a)\\ &=\widehat\delta(\widehat\delta(q,x),za). \end{aligned}$$

A segunda linha usa a hipótese de indução.

Provar que a construção está correta

No DFA anterior, afirma que, após ler $x$, a máquina está em $q_1$ se $x$ termina em $a$, em $q_2$ se termina em $ab$, e em $q_0$ nos restantes casos.

Na base, $x=\varepsilon$ não termina em nenhum desses sufixos, e a máquina está em $q_0$. No passo, acrescentar $a$ leva sempre a $q_1$. Acrescentar $b$ leva a $q_2$ exatamente quando antes havia um $a$ no fim, ou seja, quando estávamos em $q_1$. Nos outros casos leva a $q_0$. A tabela preserva o invariante em cada passo.

Como só $q_2$ é final, o invariante prova as duas direções: todas as palavras aceites terminam em $ab$, e todas as palavras terminadas em $ab$ são aceites.

Contar por restos

Um DFA não guarda contagens sem limite, mas pode guardar um resto. Para reconhecer palavras binárias cujo valor é múltiplo de $3$, usa estados $r_0,r_1,r_2$.

Se o prefixo representa $v$ e lês o bit $b$, o novo valor é $2v+b$. Logo:

$$\delta(r_i,b)=r_{(2i+b)\bmod3}.$$

Estado	$0$	$1$
$r_0$ inicial e final	$r_0$	$r_1$
$r_1$	$r_2$	$r_0$
$r_2$	$r_1$	$r_2$

$110$ representa $6$ e segue $r_0,r_1,r_0,r_0$, terminando no resto zero. Nesta convenção, zeros iniciais são permitidos e $\varepsilon$ representa zero. Se o enunciado exigir representação não vazia a começar em $1$, acrescenta um novo estado inicial não final e um poço para entradas que comecem em $0$. Não mudes a linguagem sem explicitar essa condição.

Se a entrada for um número binário lido ao contrário, a letra seguinte já não duplica o prefixo acumulado. Uma via sistemática é construir o DFA para a interpretação normal, inverter a linguagem e determinizar. Outra é guardar o resto acumulado e o peso da próxima posição módulo o divisor; ambos têm finitas possibilidades. Ao ler do bit menos significativo para o mais significativo, guarda $(r,t)$: $r$ é o resto do valor acumulado e $t$ é o peso da posição seguinte módulo 5. Começa em $(0,1)$ e, por um bit $b$, atualiza

$$(r,t)\longmapsto((r+bt)\bmod5,\;2t\bmod5).$$

Os pesos possíveis são $1,2,4,3$, repetindo esse ciclo. Para $101$:

Bit lido	$(r,t)$ antes	$(r,t)$ depois
$1$	$(0,1)$	$(1,2)$
$0$	$(1,2)$	$(1,4)$
$1$	$(1,4)$	$(0,3)$

O resto final é $0$, e o valor é $1+0+4=5$. Para exigir entrada não vazia ou um bit mais significativo igual a 1, trata também essas condições. Não reutilizes a recorrência $2v+b$ sem conferir qual ponta representa o bit menos significativo.

Combinar duas condições

Se queres guardar a paridade do número de zeros e de uns, o estado é um par $(p_0,p_1)$ de paridades. Há quatro estados. Um $0$ troca só a primeira componente; um $1$ troca só a segunda.

O estado inicial é $(\text{par},\text{par})$. Para aceitar um número par de ambos os símbolos, só esse estado é final. Para aceitar um número par de zeros ou de uns, são finais todos os pares com pelo menos uma componente par.

É a construção de produto: simular dois DFA ao mesmo tempo. Não mistures as transições com o critério de aceitação, porque o mesmo produto permite interseção, união ou diferença, escolhendo os finais. A minimização remove memória redundante depois de a construção estar correta.