05 - Autômatos Finitos Não Determinísticos

05 · Autômatos Finitos Não Determinísticos (AFND)

Resumo em 30 segundos

No AFND, para um estado e um símbolo, pode haver zero, um ou vários próximos estados: $T:K\times V\to 2^K$. Pense em várias cópias do autômato rodando em paralelo, uma para cada escolha possível. A palavra é aceita se pelo menos uma cópia termina em estado final. O não determinismo deixa os autômatos mais fáceis de projetar, mas não mais poderosos: todo AFND tem um AFD equivalente (aula 06).

Anterior: 04 - Autômatos Finitos Determinísticos · Voltar ao mapa · Próxima: 06 - Equivalência AFD e AFND

---

Slides 3 e 4: a diferença está na função de transição

	AFD	AFND
Assinatura	$T:K\times V\to K$	$T:K\times V\to 2^K$
Ao ler um símbolo	vai para um único estado	vai para um conjunto de estados (pode ser vazio)

$2^K$ é o conjunto das partes de $K$ (todos os subconjuntos). Se $|K|=3$, existem $2^3=8$ subconjuntos possíveis como destino.

Slide 5: definição formal

$M=(K,V,T,i,F)$, igual ao AFD exceto por $T:K\times V\to 2^K$. $K$ finito e não vazio, $V$ finito, $i\in K$, $F\subseteq K$.

Slides 6 a 8: representações

• Interpretação física (slide 6): um AFND é como um AFD com várias unidades de controle, todas lendo o mesmo símbolo da fita ao mesmo tempo, cada uma em um estado.
• Diagrama (slide 7): de um mesmo estado, podem sair várias setas com o mesmo rótulo (ou nenhuma).
• Tabela (slide 8): cada célula guarda um conjunto de estados. → marca o inicial, * os finais.

Slide 9: exemplo

T	a	b
→ q0	{q0, q1}	{q0, q2}
q1	{q3}	∅
q2	∅	{q3}
* q3	{q3}	{q3}

(No slide as células vazias aparecem como traço; aqui uso $\varnothing$.)

Leitura intuitiva: $q_0$ fica “esperando” em laço. Em algum momento o autômato “aposta” que começou um aa (vai para $q_1$) ou um bb (vai para $q_2$). Se a aposta der certo, chega em $q_3$ e fica lá.

L(M) = palavras que contêm aa ou bb. Conferido por programa até tamanho 10. O slide não diz qual é a linguagem; essa é a interpretação.

Slide 10: processando abbaba

O slide desenha a árvore de todas as escolhas. Um jeito mais compacto de fazer na prova é acompanhar o conjunto de estados ativos:

Passo	Lido	Estados ativos	Como
0		{q0}	inicial
1	a	{q0, q1}	$T(q_0,a)$
2	b	{q0, q2}	$T(q_0,b)\cup T(q_1,b)=\{q_0,q_2\}\cup \varnothing$
3	b	{q0, q2, q3}	$T(q_0,b)\cup T(q_2,b)$
4	a	{q0, q1, q3}	$T(q_0,a)\cup T(q_2,a)\cup T(q_3,a)$
5	b	{q0, q2, q3}
6	a	{q0, q1, q3}

Conjunto final contém $q_3\in F$: aceita. Bate com o slide (os ramos terminam em $q_3$ e em $\{q_0,q_1\}$). E bate com a intuição: abbaba contém bb.

Esse método de "conjunto de estados ativos" é a conversão AFND→AFD

Cada linha da tabela acima é um estado do AFD equivalente. A aula 06 só formaliza isso.

Slide 11: extensão de domínio

A função estendida recebe um conjunto de estados e uma palavra: $\hat{T}:2^K\times V^{\ast }\to 2^K$.

$\hat{T}(Q,\epsilon )=Q\hat{T}(Q,aw)=\hat{T}({\bigcup }_{q\in Q}T(q,a),w)$

Em palavras: aplique $T$ com o primeiro símbolo a cada estado ativo, junte tudo (união) e continue com o resto da palavra.

Aceitação: $w$ é aceita se $\hat{T}(\{i\},w)\cap F\ne \varnothing$ (pelo menos um estado final no conjunto que sobra).

Detalhe no slide 11

O slide escreve ${\bigcup }_{q\in P}$, mas o conjunto de partida se chama $Q$. O índice correto é $q\in Q$. A origem do deslize fica clara no Menezes (Def. 2.6, p. 41): lá a fórmula é $\hat{\delta }(P,aw)=\hat{\delta }({\bigcup }_{q\in P}\delta (q,a),w)$, com o conjunto chamado $P$ dos dois lados. O slide renomeou o conjunto para $Q$ em um lugar e esqueceu no outro. Repare também que aqui a recursão consome o primeiro símbolo ($aw$), enquanto no AFD (aula 04) ela consome o último ($ua$). As duas formas são equivalentes.

Slide 12: fatos e mitos

• Não determinismo é uma generalização importante: aparece em modelos de concorrência, teoria da computação e linguagens formais.
• Facilita, mas não aumenta o poder de reconhecimento de uma classe de autômatos.
• Qualquer AFND pode ser simulado por um AFD.

"Não determinístico" não é "aleatório"

O AFND não sorteia caminhos. A definição considera todos os caminhos ao mesmo tempo, e aceita se algum funciona. É uma forma de especificar, não de executar. Para executar num computador real, ou você simula o conjunto de estados (como na tabela acima) ou converte para AFD.

Complemento: o custo escondido

A equivalência tem um preço: um AFND com $n$ estados pode precisar de até $2^n$ estados no AFD. O exercício “$k$-ésimo símbolo a partir do fim é b” (abaixo) é o exemplo clássico: o AFND tem $k+1$ estados e o menor AFD equivalente tem $2^k$. Resultado padrão da teoria; não está nos slides.

Slide 13: exercícios

Todos os AFNDs abaixo foram conferidos por programa contra a descrição da linguagem.

0 e 1 terminadas em 111

$q_0$ lê qualquer coisa em laço e, ao ver um 1, “aposta” que ele é o primeiro dos três últimos. Conferido até tamanho 10.

a e b tais que o 5º símbolo antes do último seja b

O enunciado admite duas leituras:

• “5 posições antes do último” = 6º a partir do fim (o último é o 1º);
• ou simplesmente “5º a partir do fim”.

O livro resolve a dúvida. O Menezes tem um exercício quase idêntico: “o quinto símbolo da direita para a esquerda de $w$ é a” (exercício 2.2e, p. 80). Como vários exercícios dos slides saem do Menezes, a leitura mais provável é 5º a partir do fim. Para essa leitura:

$p_0$ lê qualquer coisa. Ao ler um b, aposta que esse b é o 5º do fim e depois precisa ler exatamente mais 4 símbolos quaisquer. Conferi até tamanho 11.

Se o professor quis dizer 6º a partir do fim, basta um estado a mais na cadeia (5 símbolos depois do b):

Curiosidade: o AFD equivalente à versão de 6 estados tem 32 estados alcançáveis (conferi com a construção de subconjuntos da aula 06).

0 e 1 sem 0 em sequência (sem 00)

$q_1$ significa “acabei de ler 0”. Não há transição de $q_1$ com 0, então 00 mata o caminho. Ambos os estados são finais (inclui $\epsilon$). Esse já é determinístico, e tudo bem: todo AFD também é um AFND.

L = { w ∈ {a,b,c}⁺ | aa ou bb é subpalavra e cccc é sufixo }

Três fases: (1) $q_0$ espera e aposta num aa ou bb; (2) $M$ espera qualquer coisa e aposta no início do cccc final; (3) a cadeia $C_1\to C_2\to C_3\to F$ exige os quatro c e nada depois. Conferido até tamanho 9.

Descreva a linguagem: AFND com dígitos

Transições: $q_0\stackrel{\mathrm{0..9}}{\to }{q}_1$ (final), $q_0\stackrel{\mathrm{1..9}}{\to }{q}_2$, $q_2$ com laço $\mathrm{0..9}$, $q_2\stackrel{\mathrm{0..9}}{\to }{q}_1$.

• Caminho direto $q_0\to q_1$: um dígito qualquer, inclusive 0.
• Caminho por $q_2$: primeiro dígito de 1 a 9, depois zero ou mais dígitos, depois mais um dígito.

L = números naturais sem zero à esquerda = $0\mid (\mathrm{1..9})(\mathrm{0..9}{)}^{\ast }$. Conferido por programa com um alfabeto reduzido de dígitos.

Descreva a linguagem: AFND com letras

Transições: $q_0\stackrel{A..Z}{\to }{q}_1$; $q_1$ com laço $a..z$; $q_1\stackrel{a..z}{\to }{q}_2$; $q_2\stackrel{a,e,i,o,u}{\to }{q}_3$ (final).

L = palavras que começam com uma letra maiúscula, seguem com uma ou mais minúsculas e terminam com uma vogal minúscula, com pelo menos 3 letras. ER: $(A..Z)(a..z{)}^{+}(a|e|i|o|u)$. Exemplos: Ana, Maria, Paulo. Não aceita Al (curta) nem Carlos (termina em consoante).

Detalhe: como o laço de $q_1$ também lê vogais, a ER poderia ser escrita $(A..Z)(a..z{)}^{\ast }(a..z)(a|e|i|o|u)$; as duas são iguais.

---

Aprofundamento com os livros

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

O exemplo do slide 9 é do Menezes

O AFND do slide 9 (contém aa ou bb) é o Exemplo 5 do Menezes (p. 41 e 42). O livro explica os três caminhos possíveis:

1. o laço em $q_0$, que só varre a entrada;
2. o caminho $q_0\to q_1\to q_f$, que confirma um aa;
3. o caminho $q_0\to q_2\to q_f$, que confirma um bb.

E compara com um AFD para a mesma linguagem (Exemplo 1, p. 34 e 35), que precisa “lembrar” qual foi o símbolo anterior: $q_1$ = “o anterior foi a”, $q_2$ = “o anterior foi b”. Em 08 - Tópicos Complementares dos Livros eu mostro que, se você converter o AFND do slide para AFD e depois minimizar, chega exatamente nesse AFD do livro.

O exercício do slide 13 sobre aa/bb e sufixo cccc também é do Menezes (exercício 2.3a, p. 80).

Como o Menezes descreve o não determinismo (p. 39 e 40)

Ao ler um símbolo, é como se a unidade de controle se multiplicasse, uma cópia para cada alternativa, e cada cópia seguisse sozinha, sem compartilhar nada com as outras. A palavra é aceita se existe um caminho que termina em estado final; é rejeitada se todos os caminhos rejeitam (p. 41).

Impasse, backtracking e threads (Ramos, p. 156 a 159)

O Ramos aponta duas novidades do AFND em relação ao AFD:

• Impasse: como $\varnothing \in 2^Q$, pode não existir transição e aquele caminho simplesmente morre.
• Escolha: quando há mais de um próximo estado, é preciso escolher.

	Executa	Aceita se	Rejeita se
AFD	uma única sequência de movimentos	para em configuração final	para em configuração não final
AFND	várias sequências possíveis	alguma para em configuração final	nenhuma consegue chegar a uma configuração final

(Resumo da Tabela 3.2 do Ramos, p. 157.)

Na prática, numa máquina sequencial, simula-se o AFND com busca exaustiva e backtracking: tenta um caminho, se der impasse volta e tenta outro (p. 159). O Ramos mostra isso passo a passo com a palavra abbccc num AFND para $a{b}^{\ast }{c}^{\ast }$ (Exemplo 3.12, p. 157 e 158). Em arquiteturas paralelas, cada processador pode seguir um caminho.

Backtracking ou conjunto de estados?

O método da tabela acima (acompanhar o conjunto de estados ativos) evita o backtracking: você processa todos os caminhos ao mesmo tempo, em uma passada só. É por isso que ele leva direto à construção de subconjuntos da aula 06.

Quando o AFND é bem mais simples

O Ramos compara (Exemplo 3.13, p. 158) um AFD e um AFND para “contém a subcadeia abcd”. O AFND é só uma linha de estados com laços no começo e no fim; o AFD precisa de setas de “volta” para cada caso em que o casamento falha no meio. Com o exemplo do Menezes para “termina em aaa” acontece o mesmo:

(Menezes, Exemplo 6, p. 42. A conversão para AFD está na aula 06.)

Transições vazias: o próximo passo

Os dois livros vão além dos slides e permitem transições que não leem nada, chamadas movimentos vazios ou transições em vazio ($\epsilon$). Exemplo do Menezes (Exemplo 8, p. 46) para “todo a vem antes de todo b” ($a^{\ast }{b}^{\ast }$):

O autômato pode, a qualquer momento, “pular” de $q_0$ para $q_f$ sem ler. Conferi por programa que ele aceita exatamente $a^{\ast }{b}^{\ast }$. Transições vazias também não aumentam o poder: todo AF com $\epsilon$ vira um AFND sem $\epsilon$ (Menezes Teorema 2.11, p. 48; Ramos Teoremas 3.4 e 3.5, p. 169 a 176). Detalhes em 08 - Tópicos Complementares dos Livros.

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

b.2) o décimo símbolo da direita para a esquerda é a

Mesma ideia do exercício do 5º símbolo: $q_0$ com laço em a e b; ao ler um a, aposta e segue uma cadeia de mais 9 estados que aceitam qualquer símbolo. São 11 estados no AFND. Um AFD para a mesma linguagem precisa de $2^{10}=1024$ estados, porque tem que lembrar os últimos 10 símbolos.

b.1) palavras $w_1{w}_2{w}_1$ com $w_2$ qualquer e $|w_1|=3$

Ideia de solução (minha): o AFND “chuta” $w_1$ nos três primeiros símbolos. Como $w_1$ tem só $2^3=8$ possibilidades, dá para ter um ramo para cada uma: cada ramo lê os três símbolos de $w_1$, depois faz laço em qualquer coisa e, no fim, aposta que os três últimos símbolos repetem $w_1$. Como o alfabeto e o tamanho de $w_1$ são fixos, isso é finito e a linguagem é regular. Não montei o diagrama completo porque ficaria com dezenas de estados.

Para aprofundar nos livros

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

• Menezes (3ª ed.): 2.3 Autômato Finito Não-Determinístico, p. 39 a 44; 2.4 Autômato Finito com Movimentos Vazios, p. 44 a 50; exercícios 2.3, 2.10 e 2.11, p. 80 e 81.
• Ramos, José Neto e Vega: 3.3 Autômatos Finitos, parte não determinística, p. 156 a 167; transições em vazio, p. 167 a 192.

Relacionadas: 06 - Equivalência AFD e AFND · Glossário · Flashcards