08 · Tópicos Complementares dos Livros

Por que esta nota existe

Os dois livros continuam o assunto das linguagens regulares além do ponto onde os slides param. Estes tópicos aparecem no mesmo capítulo dos livros e costumam ser as próximas aulas da disciplina: autômatos com transições vazias, conversão entre ER e autômato, minimização, Lema do Bombeamento, propriedades de fechamento, questões decidíveis e autômatos com saída (Mealy e Moore). Tudo aqui é resumo e explicação minha a partir dos livros, com os exemplos conferidos por programa.

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

Voltar ao mapa · Base: 04 - Autômatos Finitos Determinísticos, 05 - Autômatos Finitos Não Determinísticos, 06 - Equivalência AFD e AFND, 07 - Equivalência AF e GR

---

1. Autômato finito com transições vazias (AFε)

Onde: Menezes 2.4, p. 44 a 50; Ramos 3.3, p. 167 a 192.

Uma transição vazia muda de estado sem ler nenhum símbolo. A função de transição passa a ser

$\delta :Q\times (\Sigma \cup \{\epsilon \})\to 2^Q$

O Menezes descreve isso como um “não determinismo interno”: o autômato pode, a qualquer momento, seguir ou não a seta $\epsilon$, e a origem continua sendo uma alternativa (p. 45).

Fecho vazio de um estado $q$: todos os estados alcançáveis a partir de $q$ usando zero ou mais transições vazias. É o fecho reflexivo-transitivo (o $R^{\ast }$ da aula 02) da relação “tem seta $\epsilon$” (Menezes Def. 2.9, p. 46 e 47).

Para processar uma palavra: comece com o fecho vazio do estado inicial; a cada símbolo, faça as transições normais e depois aplique o fecho vazio de novo.

Menezes, Exemplo 8 (p. 46): todo a vem antes de todo b, ou seja $a^{\ast }{b}^{\ast }$

$\text{fecho}(q_0)=\{q_0,q_f\}$ e $\text{fecho}(q_f)=\{q_f\}$ (Exemplo 9, p. 47). Conferi por programa que aceita exatamente $a^{\ast }{b}^{\ast }$.

Eliminando as transições vazias (Menezes Teorema 2.11, p. 48)

Receita:

1. Para cada estado $q$ e símbolo $a$: o novo ${\delta }^{\prime }(q,a)$ é “tudo que dá para alcançar a partir de $q$ usando vazios, depois um $a$, depois vazios de novo”.
2. Um estado vira final se o seu fecho vazio contém algum estado final.

Aplicando ao exemplo acima: ${\delta }^{\prime }(q_0,a)=\{q_0,q_f\}$, ${\delta }^{\prime }(q_0,b)=\{q_f\}$, ${\delta }^{\prime }(q_f,b)=\{q_f\}$, e $q_0$ passa a ser final (porque $q_f\in \text{fecho}(q_0)$):

Conferido: aceita $a^{\ast }{b}^{\ast }$. O Ramos apresenta duas versões do algoritmo (Algoritmos 3.5 e a “versão 2”, p. 169 a 176), trabalhando direto na tabela: a linha de um estado com transição vazia recebe uma cópia das transições do estado de destino.

---

2. De expressão regular para autômato e de volta

Onde: Menezes 2.5, Teoremas 2.13 e 2.14, p. 51 a 55; Ramos 3.6, p. 206 a 216.

ER para AFε (construção por indução)

A prova é por indução no número de operadores da ER (Menezes, p. 51 a 53). Cada caso vira um “bloco” com um estado inicial e um final:

ER	Bloco
$\varnothing$	estado inicial sem saída e sem estado final
$\epsilon$	um estado que é inicial e final
$a$	$i\stackrel{a}{\to }f$
$r\mid s$	novo inicial com $\epsilon$ para os blocos de $r$ e de $s$; os finais deles vão por $\epsilon$ para um novo final
$rs$	final de $r$ ligado por $\epsilon$ ao inicial de $s$
$r^{\ast }$	novo inicial e novo final; $\epsilon$ direto do inicial para o final (aceita vazio) e $\epsilon$ do fim de $r$ de volta ao começo de $r$ (repete)

Aplicando a $a^{\ast }(aa\mid bb)$, a mesma ER do Exemplo 13 do Menezes (p. 54), sai isto (setas cinzas são $\epsilon$):

Conferi por programa que aceita exatamente $a^{\ast }(aa\mid bb)$. São 14 estados e 16 transições para uma ER curta: a construção é mecânica, não econômica. Depois se converte para AFND, AFD e minimiza.

Os "atalhos" que o Menezes proíbe (p. 53 e 54)

Na união, não junte os estados iniciais e finais dos dois blocos num só. No fecho, não reaproveite o final do bloco de $r$ como final do resultado. Esses atalhos parecem economizar estados, mas podem fazer o autômato aceitar palavras que a ER não gera. Uma boa pergunta para fazer em sala: por quê?

AF para ER

O Menezes só enuncia o resultado (Teorema 2.14, p. 55). O Ramos mostra o algoritmo (Algoritmo 3.17, p. 211 a 216): deixe o autômato com um único estado final e vá eliminando os estados intermediários um por um. Quando um estado some, cada caminho que passava por ele vira uma seta rotulada com uma ER (o laço do estado eliminado vira um ${}^{\ast }$ no meio). No fim sobra uma seta do inicial ao final, e o rótulo dela é a ER da linguagem.

---

3. Minimização de AFD

Onde: Menezes 2.8, p. 66 a 72; Ramos 3.7, p. 216 a 230.

Ideia: dois estados são equivalentes se, para qualquer palavra, os dois levam a resultados iguais (os dois aceitam ou os dois rejeitam). Estados equivalentes podem ser fundidos. O resultado é o autômato mínimo, que é único a menos do nome dos estados (Menezes Teoremas 2.27 e 2.28, p. 72).

Pré-requisitos (Menezes Def. 2.25, p. 67): o autômato tem que ser determinístico, não ter estados inacessíveis e ter função de transição total (se faltar transição, crie um estado poço $d$ para completar).

O algoritmo da tabela (Menezes Def. 2.26, p. 68 e 69)

1. Monte uma tabela com todos os pares de estados, cada par uma vez.
2. Marque todo par (final, não final): esses com certeza não são equivalentes.
3. Para cada par ainda não marcado $(p,q)$ e cada símbolo $a$, olhe o par de destinos $(\delta (p,a),\delta (q,a))$. Se esse par de destinos já está marcado, marque $(p,q)$ também. (O Menezes usa listas para propagar as marcações; na prática, repetir o passo até nada mudar dá o mesmo resultado.)
4. Os pares que sobrarem sem marca são equivalentes. Funda-os.
5. Remova estados inúteis (não finais dos quais não se chega a nenhum final).

Exemplo: o AFND do slide 9, convertido e minimizado

Convertendo o AFND “contém aa ou bb” da aula 05 com a construção de subconjuntos, saem 5 estados. Vou chamá-los de $A=[q_0]$, $B=[q_0{q}_1]$, $C=[q_0{q}_2]$, $D=[q_0{q}_1{q}_3]$, $E=[q_0{q}_2{q}_3]$ (finais: $D$ e $E$).

Tabela de pares depois do algoritmo (${\times }_1$ = marcado no passo 2, ${\times }_2$ = marcado no passo 3, $\equiv$ = equivalente):

	A	B	C	D
B	${\times }_2$
C	${\times }_2$	${\times }_2$
D	${\times }_1$	${\times }_1$	${\times }_1$
E	${\times }_1$	${\times }_1$	${\times }_1$	$\equiv$

Por que cada marca do passo 3:

• $(A,B)$: lendo a, vão para $(B,D)$, que já está marcado.
• $(A,C)$: lendo b, vão para $(C,E)$, marcado.
• $(B,C)$: lendo a, vão para $(D,B)$, marcado.
• $(D,E)$: lendo a, os dois vão para $D$; lendo b, os dois vão para $E$. Nunca chegam num par marcado: equivalentes.

Fundindo $D$ e $E$ num único estado final $q_f$:

É exatamente o AFD do Exemplo 1 do Menezes (p. 34 e 35), com $q_1$ = “o símbolo anterior foi a” e $q_2$ = “o anterior foi b”. Conferi por programa que os dois autômatos aceitam a mesma linguagem.

A ponte com a aula 02

O Ramos faz a minimização por partições (Algoritmos 3.18 e 3.19, p. 220 a 224): começa com a partição $\{F,Q-F\}$ e vai quebrando os blocos enquanto dois estados do mesmo bloco levarem, com algum símbolo, a blocos diferentes. Quando nada mais quebra, cada bloco é uma classe de equivalência e os estados do autômato mínimo são o conjunto quociente. É a matéria de partições e classes de equivalência aplicada.

---

4. Lema do Bombeamento: como provar que uma linguagem NÃO é regular

Onde: Menezes Lema 2.20, p. 61 a 63; Ramos Teorema 3.16, p. 233 a 239.

A intuição

Um AFD tem $n$ estados. Para ler uma palavra de tamanho $n$ ou mais, ele passa por $n+1$ estados ou mais, então algum estado se repete (princípio da casa dos pombos). O trecho da palavra lido entre as duas visitas forma um ciclo, e dá para repetir esse ciclo quantas vezes quiser (ou nenhuma) sem mudar o resultado.

O enunciado

Se $L$ é regular, existe uma constante $n$ tal que toda palavra $w\in L$ com $|w|\ge n$ pode ser escrita como $w=uvz$ com

• $|uv|\le n$,
• $|v|\ge 1$,
• $u{v}^{i}z\in L$ para todo $i\ge 0$.

Como usar (por absurdo)

1. Suponha que $L$ é regular. Então existe o $n$ do lema (você não precisa saber o valor).
2. Escolha uma palavra $w\in L$ com $|w|\ge n$, escrita em função de $n$.
3. Mostre que qualquer divisão $w=uvz$ que respeite as condições gera algum $u{v}^{i}z\notin L$.
4. Contradição: $L$ não é regular.

$\{a^n{b}^n\mid n\ge 0\}$ não é regular (Menezes Ex. 19, p. 63; Ramos Ex. 3.52, p. 237)

Suponha que é regular, com constante $n$. Tome $w=a^n{b}^n$. Como $|uv|\le n$, o pedaço $uv$ está todo dentro dos a, então $v=a^k$ com $k\ge 1$. Bombeando uma vez a mais: $u{v}^{2}z=a^{n+k}{b}^n$, que tem mais a do que b e está fora da linguagem. Contradição.

O Menezes usa essa mesma palavra para provar que “mesmo número de a e b” não é regular. E isso fecha a promessa da aula 03: a linguagem $0^n{1}^n$ do slide 11 é livre de contexto, mas não é regular.

Outros exemplos do Ramos (p. 238): $0^{k}10^k$ (o mesmo número de zeros dos dois lados do 1), $a^{k^2}$ (comprimentos quadrados perfeitos) e $a^p$ com $p$ primo. Nenhuma é regular.

O lema só serve para um lado

O lema diz uma coisa que toda linguagem regular satisfaz. Ele serve para provar que uma linguagem não é regular. Para provar que é regular, mostre uma ER, um AF ou uma gramática regular (Ramos, p. 237).

---

5. Propriedades de fechamento

Onde: Menezes Teorema 2.21, p. 63 e 64; Ramos 3.10, p. 239 em diante.

A classe das linguagens regulares é fechada (no sentido da aula 02) para:

Operação	Por quê
União	$r\mid s$ é ER
Concatenação	$rs$ é ER
Fecho	$r^{\ast }$ é ER
Complemento	pegue um AFD total (com estado poço se preciso) e troque finais por não finais
Interseção	$L_1\cap L_2=\overline{\overline{L_1}\cup \overline{L_2}}$ (De Morgan)

Por que o AFD precisa ser total no complemento

Se a função é parcial, o autômato rejeita palavras “por indefinição” no meio do caminho. Trocar finais por não finais não muda isso, então essas palavras continuariam rejeitadas nos dois autômatos. O Menezes completa com um estado $d$ antes de trocar (p. 63 e 64).

Truque de prova (complemento meu)

Fechamento também ajuda a provar que algo não é regular. Exemplo: $L=\{w\mid \#a=\#b\}$. Se $L$ fosse regular, $L\cap a^{\ast }{b}^{\ast }$ também seria (interseção de regulares). Mas $L\cap a^{\ast }{b}^{\ast }=\{a^n{b}^n\}$, que não é regular. Logo $L$ não é regular.

---

6. Perguntas que um algoritmo consegue responder

Onde: Menezes Teoremas 2.22 e 2.23, p. 64 a 66; Ramos 3.11, p. 247 em diante.

Para um AF com $n$ estados:

Pergunta	Como decidir
$L$ é vazia?	teste todas as palavras com menos de $n$ símbolos; se nenhuma é aceita, é vazia
$L$ é infinita?	é infinita se e só se aceita alguma palavra com $n\le |w|<2n$ (pelo bombeamento, dá para repetir o ciclo)
$L_1=L_2$?	construa $(L_1\cap \overline{L_2})\cup (\overline{L_1}\cap L_2)$ e teste se é vazia

Todas usam as propriedades de fechamento. Na prática existem métodos mais rápidos (o próprio Menezes sugere no exercício 2.16, p. 83, usar remoção de estados inacessíveis e minimização).

---

7. Autômatos com saída: Mealy e Moore

Onde: Menezes 2.9, p. 72 a 79; Ramos 3.8 (Transdutores Finitos), p. 230 a 233.

Um AF comum só responde sim ou não. Um transdutor também escreve numa fita de saída (sem poder ler de volta, então a saída não vira memória).

	Mealy	Moore
Saída associada a	cada transição	cada estado
Rótulo no diagrama	lido / escrito na seta	a saída anotada no estado
Entrada vazia	não escreve nada	escreve a saída do estado inicial

Os dois modelos são equivalentes, exceto para a entrada vazia (Menezes Teoremas 2.31 e 2.32, p. 76 a 79). Para simular Mealy com Moore, às vezes é preciso duplicar estados, um para cada saída diferente que chega nele.

Mealy que compacta espaços em branco (Menezes, Exemplo 24, p. 79)

a é qualquer caractere do texto e B é o espaço em branco. O estado $p$ lembra “acabei de escrever um branco”, e brancos seguintes não são escritos:

Conferi por programa que a saída é sempre a entrada com cada sequência de brancos trocada por um único branco.

Onde isso aparece em compiladores

O Menezes (Exemplo 23, p. 76) descreve um analisador léxico como Máquina de Moore: cada estado final corresponde a um tipo de token e tem como saída o código desse token; os estados não finais têm saída vazia. É a ponte direta entre esta disciplina e a matéria de compiladores.

---

Exercícios dos livros para praticar estes tópicos

• Menezes (p. 80 a 84): 2.7 (ER para AF), 2.8 (ER até gramática, passando por todos os formalismos), 2.9 (minimização), 2.10 (por que o AF sempre para, e o caso de ciclo de transições vazias), 2.14 (provar que $\{ww\}$ e $\{a^n{b}^n\}$ não são regulares), 2.16 e 2.17 (decidibilidade), 2.19 (Mealy e Moore convertendo US$paraR$).
• Ramos: exercícios do capítulo 3 a partir da p. 275.

Para aprofundar nos livros

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

• Menezes (3ª ed.): 2.4, p. 44 a 50; 2.5 (Teoremas 2.13 e 2.14), p. 51 a 55; 2.7, p. 60 a 66; 2.8, p. 66 a 72; 2.9, p. 72 a 79; exercícios, p. 80 a 84.
• Ramos, José Neto e Vega: 3.3 (transições em vazio), p. 167 a 192; 3.6, p. 206 a 216; 3.7, p. 216 a 230; 3.8, p. 230 a 233; 3.9, p. 233 a 239; 3.10 e 3.11, a partir da p. 239.

Relacionadas: Glossário · Flashcards · Referências - Livros