04 - Autômatos Finitos Determinísticos

04 · Autômatos Finitos Determinísticos (AFD)

Resumo em 30 segundos

Um AFD é uma máquina com memória finita (só guarda o estado atual) que lê a palavra da esquerda para a direita, um símbolo por vez, e no fim responde sim ou não. Formalmente $M=(K,V,T,i,F)$. É determinístico porque, para cada estado e símbolo, existe exatamente um próximo estado. Aceita a palavra se termina em um estado de $F$. As linguagens aceitas por AFDs são as regulares.

Anterior: 03b - Expressões Regulares · Voltar ao mapa · Próxima: 05 - Autômatos Finitos Não Determinísticos

---

Slides 3 e 4: introdução

• AF é um dispositivo (software ou hardware) reconhecedor/aceitador que processa uma quantidade finita de informação em cada instante.
• Recebe uma sequência de símbolos e a saída indica se ela pertence ou não à linguagem.
• Tem um número finito de estados.
• O estado atual resume o passado: tudo o que importa sobre os símbolos já lidos está codificado no estado. Não há outra memória.

Duas versões (slide 4):

	AFD	AFND
Transições por símbolo lido	exatamente uma	zero ou mais
Próximo estado	único	nenhum, um ou vários
Reconhece	linguagens regulares	as mesmas linguagens regulares

O AFND fica para a aula 05, e a prova de que os dois têm o mesmo poder está na aula 06.

Slide 5: definição formal

$M=(K,V,T,i,F)$

Componente	Significado	Restrição
$K$	conjunto de estados	finito e não vazio
$V$	alfabeto de entrada	finito
$T$	função de transição	$T:K\times V\to K$
$i$	estado inicial	$i\in K$
$F$	estados finais (de aceitação)	$F\subseteq K$

Aceitação: partindo de $i$ e processando a palavra inteira, o autômato termina em um estado de $F$.

Erro comum de prova

Passar por um estado final no meio da palavra não conta. Só importa o estado depois do último símbolo.

Notação em outros livros

Na literatura em geral é comum ver $M=(Q,\Sigma ,\delta ,q_0,F)$: $Q$ = estados, $\Sigma$ = alfabeto, $\delta$ = transição. É a mesma coisa com outros nomes. Confira a ordem dos componentes no livro que estiver usando.

Slide 6: o modelo físico

• Fita com a entrada, um símbolo por célula.
• Cabeçote de leitura: lê uma célula e só anda para a direita (uma passada, sem voltar, sem escrever).
• Controle finito: guarda o estado atual $q$ e aplica a função de transição a cada símbolo lido.

Três representações do mesmo AFD

Slides 7 a 9. O mesmo autômato de exemplo aparece em três formas.

Representação algébrica

$K=\{q_0,q_1,q_2,q_3\}$, $V=\{a,b\}$, $i=q_0$, $F=\{q_3\}$ e

$T(q_0,a)=q_1$, $T(q_0,b)=q_2$, $T(q_1,a)=q_0$, $T(q_1,b)=q_3$, $T(q_2,a)=q_3$, $T(q_2,b)=q_0$, $T(q_3,a)=q_2$, $T(q_3,b)=q_1$.

Diagrama de transições

• Círculo = estado. Seta rotulada = transição com aquele símbolo.
• Seta “solta” apontando para um estado = inicial.
• Círculo duplo = estado final.

Tabela de transições

T	a	b
→ q0	q1	q2
q1	q0	q3
q2	q3	q0
* q3	q2	q1

Convenções: estados na primeira coluna, alfabeto na primeira linha, → marca o inicial, * marca finais. Cada célula é o destino. Exemplo: em $q_2$ lendo a, vai para $q_3$.

Quando usar cada uma

Diagrama: melhor para entender e simular na mão. Tabela: melhor para programar e para algoritmos como a conversão AFND→AFD. Algébrica: é a definição formal que a prova pede quando diz “descreva formalmente”.

Slide 10: interpretação (descobrir a linguagem)

A técnica: associar a cada estado uma propriedade do que já foi lido.

Estado	nº de a	nº de b
→ q0	par	par
q1	ímpar	par
q2	par	ímpar
* q3	ímpar	ímpar

Ler a troca a paridade de a (anda na horizontal do diagrama); ler b troca a de b (anda na vertical). Como $F=\{q_3\}$:

L(M) = palavras com número ímpar de a e número ímpar de b (não necessariamente iguais).

Conferido por programa para todas as palavras até tamanho 10.

Simulação passo a passo com abab

Passo	Lido	Estado
0		q0
1	a	q1
2	b	q3
3	a	q2
4	b	q0

Termina em $q_0\notin F$: rejeita. Faz sentido: abab tem 2 a e 2 b (pares). Note que passou por $q_3$ no passo 2 e isso não conta.

Slide 11: extensão de domínio (T-chapéu)

$T$ lê um símbolo. Para ler uma palavra, define-se $\hat{T}:K\times V^{\ast }\to K$ recursivamente:

$\hat{T}(q,\epsilon )=q\hat{T}(q,ua)=T(\hat{T}(q,u),a)(u\in V^{\ast },a\in V)$

• Ler a palavra vazia não muda o estado.
• Para ler $u$ seguido de $a$: primeiro processa $u$, depois dá um passo com $a$.
• $\hat{T}(q,u)=p$ significa: partindo de $q$, chega em $p$ em exatamente $|u|$ transições.

Aceitação formal: $u$ é aceita se $\hat{T}(q_0,u)\in F$. Assim $L(M)=\{u\in V^{\ast }\mid \hat{T}(q_0,u)\in F\}$.

Qualquer linguagem aceita por um AF é chamada regular.

Isso é um laço for

type Estado = string;
function aceita(T: Record<string, Estado>, inicial: Estado, finais: Set<Estado>, w: string): boolean {
  let q = inicial;                 // T̂(q0, ε) = q0
  for (const a of w) {             // T̂(q0, ua) = T(T̂(q0, u), a)
    const prox = T[`${q},${a}`];
    if (prox === undefined) return false; // transição indefinida: rejeita
    q = prox;
  }
  return finais.has(q);
}

A recursão da definição vira uma variável que acumula o estado.

Exercícios

Slides 12 a 14. Todas as respostas abaixo foram conferidas simulando os autômatos por programa em todas as palavras até tamanho 10.

Exercício 1 (slide 12): linguagem do diagrama

Resolução

1. Se a palavra começa com b, vai para $q_3$, um estado poço (não final, só tem laços). Nunca aceita. Então toda palavra aceita começa com a.
2. Depois do primeiro a o autômato fica entre $q_1$ e $q_2$. Repare: de qualquer um dos dois, ler a leva a $q_2$ e ler b leva a $q_1$. Ou seja, estar em $q_2$ significa “o último símbolo lido foi a”.
3. $q_2$ é o único final. Mas uma palavra de tamanho 1 (a) termina em $q_1$.

L = palavras que começam e terminam com a, com pelo menos 2 símbolos = $a(a|b{)}^{\ast }a$.

Exercício 2 (slide 12): linguagem da tabela

T	a	b
→ q0	q1	q3
q1	q2	q0
* q2	q3	q1
q3	q0	q2

Resolução

Numere os estados $q_0=0,q_1=1,q_2=2,q_3=3$. Ler a soma 1 (módulo 4) e ler b subtrai 1 (módulo 4). Confira: $T(q_3,a)=q_0$ porque $3+1=4\equiv 0$; $T(q_0,b)=q_3$ porque $0-1\equiv 3$.

O estado é sempre $(\#a-\#b)\mathrm{mod}4$. Com $F=\{q_2\}$:

$L=\{w\in \{a,b{\}}^{\ast }\mid (\#a(w)-\#b(w))\mathrm{mod}4=2\}$

Exemplos aceitos: aa, bb, aaab… Rejeitados: ab, a.

Exercício 3 (slide 13): tabela com lacunas

(No slide as lacunas aparecem como um traço; aqui uso ∅ para “sem transição”.)

T	a	b
→ q0	q1	∅
q1	q1	q2
* q2	∅	∅

Resolução

Descrição formal: $M=(\{q_0,q_1,q_2\},\{a,b\},T,q_0,\{q_2\})$ com $T(q_0,a)=q_1$, $T(q_1,a)=q_1$, $T(q_1,b)=q_2$ e as demais indefinidas.

Linguagem: um ou mais a seguidos de exatamente um b: $L=\{a^{n}b\mid n\ge 1\}=a^{+}b$.

Observação: com lacunas, $T$ não é uma função total $K\times V\to K$ como exige o slide 5. Para completar, acrescente um estado poço $q_e$ (não final) e mande todas as lacunas para ele, inclusive $T(q_e,a)=T(q_e,b)=q_e$. A linguagem não muda.

Exercício 4 (slide 13): diagrama com 0 e 1

Resolução

Olhando o slide ampliado: $q_0$ e $q_1$ são ambos finais (círculo duplo); $q_0$ tem laço em 0; $q_0\stackrel{1}{\to }{q}_1$; $q_1\stackrel{0}{\to }{q}_0$; e não existe transição de $q_1$ com 1.

Descrição formal: $M=(\{q_0,q_1\},\{0,1\},T,q_0,\{q_0,q_1\})$.

T	0	1
→* q0	q0	q1
* q1	q0	∅

Linguagem: estar em $q_1$ significa “o último foi 1”. Ler outro 1 ali não tem transição, então a palavra morre. Como os dois estados são finais, aceita tudo o que não morre:

$L=\{w\in \{0,1{\}}^{\ast }\mid w\text{ na˜o conteˊm }11\}$

Inclui $\epsilon$, porque o inicial é final.

Na primeira versão deste guia eu não tinha certeza se $q_1$ era final. Com o slide ampliado, confirmei que é.

Exercício 5 (slide 14): construir AFDs

Inteiros com ou sem sinal

Sinal opcional (+ ou -), depois pelo menos um dígito. Equivale à ER $(+|-{)}^{?}{D}^{+}$. Conferido contra essa ER.

Reais com uma casa decimal e sinal opcional

Sinal opcional, um ou mais dígitos, ponto obrigatório, exatamente um dígito. Só dec é final. Equivale a $(+|-{)}^{?}{D}^{+}.D$.

Estas são uma construção possível, não a única. Se o professor quiser proibir zeros à esquerda (como em ERs léxicas da aula 03b), acrescente um estado separado para o dígito 0 inicial.

Exercício 6 (slide 14): verificar sentenças

T	0	1
→* q0	q2	q1
q1	q3	q0
q2	q0	q3
q3	q1	q2

Resolução

Invariante: estado = (paridade de 0s, paridade de 1s). $q_0$=(par,par), $q_1$=(par,ímpar), $q_2$=(ímpar,par), $q_3$=(ímpar,ímpar). As 8 transições respeitam isso. $F=\{q_0\}$.

110101: $q_0\stackrel{1}{\to }{q}_1\stackrel{1}{\to }{q}_0\stackrel{0}{\to }{q}_2\stackrel{1}{\to }{q}_3\stackrel{0}{\to }{q}_1\stackrel{1}{\to }{q}_0$. Termina em $q_0$: aceita. (Dois 0s e quatro 1s, ambos pares.)

1011: $q_0\stackrel{1}{\to }{q}_1\stackrel{0}{\to }{q}_3\stackrel{1}{\to }{q}_2\stackrel{1}{\to }{q}_3$. Termina em $q_3$: rejeita. (Um 0 e três 1s.)

L = {w | w tem número par de 0s e de 1s}: é exatamente a linguagem do AFD, então reconhece. A justificativa é o invariante acima.

---

Mapa da aula

flowchart LR
  AF[Autômato Finito] --> D[Definição<br/>K, V, T, i, F]
  AF --> R[Representações]
  R --> R1[Algébrica]
  R --> R2[Diagrama]
  R --> R3[Tabela]
  AF --> I[Interpretação<br/>invariante por estado]
  AF --> E["Extensão T̂<br/>ler palavras inteiras"]
  E --> AC["Aceita se T̂(i,w) ∈ F"]
  AC --> LR[Linguagem regular]

Aprofundamento com os livros

Páginas das edições da sua pasta: Menezes 3ª edição (2000) e Ramos, José Neto e Vega (Bookman).

Sistemas de estados finitos no mundo real (Menezes 2.1, p. 32)

Um sistema de estados finitos tem entradas e saídas discretas e um número finito de estados, e cada estado resume só o que do passado importa para decidir o próximo passo. Exemplos e contraexemplos do Menezes:

• Elevador: não guarda o histórico de chamadas; o estado é “andar atual + direção”.
• Analisador léxico e ferramentas de busca em editores de texto: o estado memoriza a estrutura do prefixo já lido.
• Cérebro: em tese seria finito, mas o número de estados é tão grande que o modelo não ajuda.
• Computador: também é finito na prática, mas estudar o que é computável exige memória sem limite, por isso se usa a Máquina de Turing.

As três partes e as três formas de parar (Menezes 2.2, p. 33 a 35)

O Menezes descreve o AFD como fita (finita, só leitura, a palavra ocupa a fita toda), unidade de controle (estado atual + cabeça que só anda para a direita) e programa (a função de transição). Um detalhe importante: para ele a função de transição é parcial. Isso dá três formas de parar:

Situação no fim do processamento	Resultado
Leu tudo e está num estado final	aceita
Leu tudo e está num estado não final	rejeita
Encontrou uma transição indefinida no meio	rejeita na hora

Um AFD sempre para

Como cada passo consome um símbolo e a palavra é finita, não existe laço infinito (Menezes, p. 35). Isso deixa de ser verdade em modelos mais poderosos, como a Máquina de Turing.

O Ramos chama a atenção para o custo da função total (p. 151): com $n$ estados e $m$ símbolos, um AFD total tem exatamente $m\cdot n$ transições. É o que faz a tabela ficar sem buracos.

T-chapéu consumindo pelo começo ou pelo fim

Fonte	Definição recursiva
Slides (e o Ramos em outra forma)	$\hat{T}(q,ua)=T(\hat{T}(q,u),a)$: lê $u$ e depois o último símbolo
Menezes (Def. 2.2, p. 36)	$\hat{\delta }(q,aw)=\hat{\delta }(\delta (q,a),w)$: lê o primeiro símbolo e depois o resto

As duas dão o mesmo resultado. A do Menezes é a que um laço for implementa diretamente, e ele mostra o passo a passo com a palavra abaa (Exemplo 2, p. 36).

Configurações e a relação ⊢ (Ramos, p. 151 e 152)

O Ramos descreve o processamento como uma sequência de configurações $(q,y)$: o estado atual e o que ainda falta ler. Um passo é $(q,ay)⊢(p,y)$ se $T(q,a)=p$. Com o AFD de paridade desta aula e a palavra abab:

$(q_0,abab)⊢(q_1,bab)⊢(q_3,ab)⊢(q_2,b)⊢(q_0,\epsilon )$

A palavra é aceita se $(q_0,w){⊢}^{\ast }(q_f,\epsilon )$ com $q_f\in F$. Aqui termina em $q_0\notin F$: rejeita. Repare que ${⊢}^{\ast }$ é o fecho reflexivo-transitivo de $⊢$, de novo o $R^{\ast }$ da aula 02.

Aceita e rejeita dividem tudo (Menezes, p. 37)

$\text{ACEITA}(M)$ e $\text{REJEITA}(M)$ não têm palavras em comum e juntas formam ${\Sigma }^{\ast }$. Uma é o complemento da outra. Dois autômatos são equivalentes quando aceitam a mesma linguagem, e uma linguagem aceita por algum AFD é chamada regular (Def. 2.3 e 2.4).

Mesmo programa, linguagens opostas (Menezes, Exemplo 3, p. 37 e 38)

Dois autômatos com um único estado $q_0$ e laço em a e b. No primeiro, $F=\varnothing$: aceita $\varnothing$. No segundo, $F=\{q_0\}$: aceita ${\Sigma }^{\ast }$. As funções de transição são idênticas; o que muda é só o conjunto de estados finais. Boa pergunta de prova: “o que diferencia os dois?”

O estado como memória, generalizado (Ramos, Exemplo 3.11, p. 154 e 155)

O slide 10 usa 4 estados para acompanhar a paridade de a e de b. O Ramos faz o mesmo com três símbolos: 8 estados com nomes como PPP, IPP, III (par ou ímpar de a, de b e de c). Com $F=\{III\}$, aceita palavras com quantidades ímpares de a, b e c. Trocar $F$ muda a linguagem sem mexer nas transições: com $F=\{PPP\}$ aceita “tudo par”.

Regra geral que dá para tirar daqui: para acompanhar a paridade de $k$ símbolos, bastam $2^k$ estados.

Eficiência (Menezes, p. 66)

Um AFD decide se aceita em tempo proporcional ao tamanho da entrada, qualquer que seja o autômato. Não existe algoritmo de reconhecimento mais rápido do que isso em geral. Dá para melhorar só o número de estados (o tamanho do programa), com o algoritmo de minimização explicado em 08 - Tópicos Complementares dos Livros.

Exercícios extras do Menezes (2.2, p. 80)

Construa AFDs sobre $\{a,b\}$. Respostas minhas, conferidas por programa até tamanho 12.

a) palavras que contêm aaa

Os estados contam quantos a seguidos acabaram de aparecer: $q_0$ (nenhum), $q_1$, $q_2$, e $q_3$ (já achou aaa, fica lá).

b) palavras com sufixo aa

Parecido, mas sem estado “preso”: ler b sempre volta para $q_0$, porque um b no fim estraga o sufixo.

c) número ímpar de a e ímpar de b

É exatamente o AFD de paridade do slide 10 desta aula.

d) (par de a e ímpar de b) ou (par de b e ímpar de a)

Pegadinha: se exatamente uma das contagens é ímpar, a soma é ímpar; e se o tamanho é ímpar, exatamente uma contagem é ímpar. Então a linguagem é simplesmente palavras de tamanho ímpar, e bastam 2 estados:

e) o quinto símbolo da direita para a esquerda é a

Um AFD precisa lembrar os últimos 5 símbolos, então precisa de $2^5=32$ estados. Com não determinismo bastam 6 (ver o exercício equivalente na aula 05). É o exemplo clássico de explosão de estados na conversão AFND→AFD.

Para aprofundar nos livros

Onde ler (páginas das edições da sua pasta)

• Menezes (3ª ed.): 2.1 Sistema de Estados Finitos, p. 32; 2.2 Autômato Finito, p. 33 a 38; eficiência, p. 66; exercícios 2.2, 2.10 e 2.24, p. 80 a 84.
• Ramos, José Neto e Vega: 3.3 Autômatos Finitos (parte determinística), p. 150 a 155; Tabela 3.2 (aceitação em AFD e AFND), p. 157.

Relacionadas: 05 - Autômatos Finitos Não Determinísticos · 06 - Equivalência AFD e AFND · Glossário · Flashcards