flowchart LR
ESP["especificação<br/>escrita por gente"]
ER["expressão regular<br/>GERADOR<br/>diz como produzir as cadeias"]
AFD["autômato finito<br/>RECONHECEDOR<br/>diz se a cadeia pertence"]
EXEC["execução sobre a entrada<br/>um passo por símbolo"]
ESP --> ER
ER -->|"tradução automática<br/>teorema de Kleene"| AFD
AFD --> EXEC
ER -.->|"curta, legível,<br/>não se executa"| ER
AFD -.->|"volumosa, ilegível,<br/>trivial de executar"| AFD
1 Módulo 3: Autômatos Finitos Determinísticos — Resumo
Esta é a versão de revisão. Recapitulo aqui, em ritmo de véspera, o módulo em que a teoria começa a rodar; nada é demonstrado por inteiro, e para isso existem a versão completa do material deste módulo e o livro. Confira com este texto se você consegue ler a descrição de um conjunto de cadeias, desenhar a máquina que o reconhece e traduzi-la em estrutura de dados.
Você tem uma expressão regular na mão e uma cadeia de trinta caracteres. Pertence ou não pertence? Até o módulo anterior a resposta honesta era: não sei dizer, só sei gerar cadeias e comparar — e conjunto infinito não cabe em memória.
1.1 Descrever não é decidir: a máquina que só sabe onde está
O caminho não foi melhorar a enumeração, foi sair do lado dos geradores e passar para o dos reconhecedores. Uma expressão regular é um gerador: curta, legível e que não se executa. Um autômato é um reconhecedor: volumoso e trivial de executar. A saída dessa tensão é a que qualquer engenheiro adotaria — especifica-se na forma conveniente para gente e traduz-se para a conveniente para máquinas, nos dois sentidos, pelo teorema de Kleene.
A máquina do primeiro andar da hierarquia é constrangedoramente simples: lê a entrada uma vez, da esquerda para a direita, sem voltar atrás e sem escrever nada, e toda a memória que tem é saber em qual de um número finito de situações se encontra. A tese que eu defendo é que a fraqueza é a origem da utilidade. E cuidado com “memória finita”, que ao pé da letra não distingue nada: o que caracteriza o autômato finito é a memória limitada por uma constante fixada antes de ver a entrada.
Guarde esta frase. Tudo o que a máquina sabe sobre o que já leu está codificado em qual estado ela ocupa, e se dois prefixos levam ao mesmo estado ela os considera indistinguíveis daí em diante. É o critério de projeto deste módulo, a base da minimização e o mecanismo do lema do bombeamento.
Quanto à origem, tenho impaciência com o “os autômatos surgiram como modelo abstrato de computação”: as origens são datáveis e independentes — McCulloch e Pitts modelando o neurônio como dispositivo de limiar em 1943, Kleene em relatório de 1951 publicado em 1956 na coletânea Automata Studies, a engenharia de circuitos sequenciais com Huffman, Mealy e Moore entre 1954 e 1956, e Rabin e Scott em 1959. E o modelo mais fraco é o mais usado por três propriedades que só ele reúne: um passo por símbolo, previsibilidade e decidibilidade completa.
1.2 A definição formal, componente por componente
Um autômato finito determinístico é uma quíntupla
M = (Q, \Sigma, \delta, q_0, F),
em que Q é um conjunto finito e não vazio de estados, \Sigma é um alfabeto finito e não vazio, \delta : Q \times \Sigma \to Q é uma função total, q_0 \in Q é o estado inicial e F \subseteq Q é o conjunto dos estados finais. A definição descreve o dispositivo parado; o comportamento vem numa segunda camada.
flowchart TB
M["autômato finito determinístico<br/>quíntupla"]
Q["Q — conjunto finito de estados<br/>a única memória da máquina"]
S["Sigma — alfabeto finito<br/>define quais entradas fazem sentido"]
D["delta — função de transição TOTAL<br/>um destino, e só um, por par"]
I["q0 — estado inicial<br/>um só, porque escolha é proibida"]
F["F — subconjunto dos estados finais<br/>pode ser vazio, pode ser todo Q"]
M --> Q
M --> S
M --> D
M --> I
M --> F
Nada além de finitude é exigido de Q: estados são elementos abstratos, e os nomes falantes são conveniência nossa — por isso, na implementação, podem ser inteiros com total fidelidade à teoria. É em \delta que mora o comportamento, e sobre ela a definição faz a exigência mais atropelada em sala: ela é total, todo par de estado e símbolo tem destino único. O estado inicial é um só; já F é subconjunto qualquer, e o caso em que ele contém q_0 é fonte de erro sistemático — se a linguagem contém a cadeia vazia, o inicial tem de ser final; se não contém, não pode ser. É a primeira coisa a conferir num autômato recém-desenhado.
O adjetivo “determinístico” é carregado pela palavra “função”: cada par tem no máximo um destino e pelo menos um destino. No módulo seguinte abandonaremos a unicidade, e abandoná-la derruba junto a totalidade, porque o conjunto vazio passa a ser resposta legítima. Daí também a assimetria da definição: vários estados iniciais introduziriam escolha logo no começo, e escolha é o que o determinismo proíbe.
1.3 Pondo a máquina em movimento
Vale a paciência com este vocabulário: é nele que se demonstram, adiante, a determinização, a minimização e o bombeamento. Uma configuração instantânea é o par (q, w) formado pelo estado corrente e pela porção da entrada ainda não lida — duas componentes e mais nada; a de um autômato de pilha tem três, e a de uma máquina de Turing descreve a fita inteira, de modo que o tamanho da configuração mede o poder do modelo. O passo de computação é (q, aw) \vdash_M (\delta(q,a), w), e como cada passo consome um símbolo, a computação sobre uma cadeia de comprimento n tem n passos e termina sempre. Para a aceitação precisamos do efeito de uma cadeia inteira, e a maneira limpa é definir por indução a função de transição estendida:
\hat\delta(q, \varepsilon) = q, \qquad \hat\delta(q, wa) = \delta\big(\hat\delta(q, w),\, a\big).
Leia a segunda cláusula devagar, porque a ordem das operações é a confusão mais comum daqui: para saber onde wa leva, descubra antes onde o prefixo w leva e só então aplique um passo com a — a recursão desce pelo prefixo, não pelo primeiro símbolo. Daí sai o primeiro resultado do módulo: \hat\delta(q, xy) = \hat\delta(\hat\delta(q, x), y), que sustenta o traçado incremental, a correção do casamento mais longo no analisador léxico e o argumento do bombeamento. Com isso, L(M) = \{ w \in \Sigma^* \mid \hat\delta(q_0, w) \in F \} é a linguagem reconhecida, e uma linguagem é regular quando existe algum autômato finito determinístico que a reconhece.
Duas armadilhas. A aceitação depende apenas do estado em que a computação termina, e não do caminho — quem traça à mão costuma dar a cadeia por aceita assim que passa por um estado final. E dizer que uma linguagem é regular é afirmar que existe um autômato: para mostrar que não é, é preciso descartar todos os autômatos possíveis de uma vez. Fecha o vocabulário a equivalência, relação entre comportamentos e não entre estruturas: como cada linguagem regular tem um autômato mínimo canônico, o projeto manual tem gabarito objetivo, não é matéria de gosto.
1.4 Diagrama, tabela e a conversão entre eles
Ninguém escreve autômatos como quíntuplas. O diagrama de estados torna visível a estrutura de caminhos — o ciclo, o estado do qual não se sai —, e não escala: com quarenta estados vira um emaranhado. A tabela de transição indexa linhas por estados e colunas por símbolos, e é executável: salta-se a cada símbolo para a linha indicada pela célula e confere-se ao fim se ela é final. É um laço com uma indexação por iteração, e por isso a tabela é a representação da máquina; em compensação, esconde a topologia.
| Estado | a | b |
|---|---|---|
| q_0 (inicial e final) | q_1 | q_0 |
| q_1 | q_2 | q_1 |
| q_2 | q_0 | q_2 |
Nele, o b não altera a contagem e a coluna dele é a diagonal, enquanto o a avança e a dele é a permutação cíclica — três estados porque a informação retida é o resto, não a contagem. As conversões são mecânicas e precisam ficar automáticas: do diagrama para a tabela, uma linha por círculo e cada seta expandida, de modo que uma seta rotulada com dez símbolos produza dez células; da tabela para o diagrama, o inverso. Ao terminar, confira as marcas e a contagem: com n estados sobre k símbolos há exatamente n \times k células.
1.5 O estado de erro e a completude
Ninguém desenha as cem setas que um alfabeto de cem símbolos exigiria de cada estado: declaram-se as transições interessantes e entende-se que cair numa transição em branco é rejeitar. Violação da definição ou abreviação legítima? Abreviação, legitimada pelo teorema do completamento: para todo autômato de transição parcial existe um de transição total que reconhece a mesma linguagem, com no máximo um estado a mais — acrescenta-se d, manda-se para ele toda transição indefinida, e as que saem dele voltam para ele mesmo. Esse estado morto, não final e absorvente, sempre existe, mesmo quando não é desenhado: a escolha entre as duas formas é de representação, não de semântica.
flowchart LR
Q0(["q0 inicial"])
Q1["q1"]
Q2(["q2 final"])
D["d — estado morto<br/>não final e absorvente"]
Q0 -->|"sinal"| Q1
Q0 -->|"dígito"| Q2
Q1 -->|"dígito"| Q2
Q2 -->|"dígito"| Q2
Q0 -.->|"qualquer outro símbolo"| D
Q1 -.->|"qualquer outro símbolo"| D
Q2 -.->|"qualquer outro símbolo"| D
D -.->|"todo símbolo do alfabeto"| D
Decorre daí uma distinção com consequência no analisador léxico: ou a cadeia é consumida inteira e a máquina para em estado não final, ou aparece um símbolo sem transição. São mensagens diferentes — “faltou alguma coisa” e “isto não pertence aqui” —, e a informação que as distingue some se o reconhecedor devolver apenas um booleano.
1.6 Projetar autômatos a partir de descrições informais
Esta é a parte que não se aprende lendo. O que eu ofereço é uma pergunta única e o catálogo dos erros que se repetem.
A pergunta de projeto. Li um prefixo da entrada e a leitura continua: qual é a menor informação sobre esse prefixo que preciso reter para decidir corretamente o resto da computação? Cada resposta possível é um estado.
A força está no “menor”. Sempre dá para responder “preciso lembrar o prefixo inteiro”, e isso produz infinitos estados, o que não é um autômato. Para as cadeias com tantos a quanto b, a resposta é a diferença entre as contagens, um inteiro sem limite — e não há autômato finito. Repara que o método avisa que vai falhar, e pelo motivo certo. Na prática: exemplos de aceitação e de rejeição escritos antes de desenhar, estados nomeados por significado, finais marcados antes das transições e completude conferida estado por estado.
Aplique ao caso mais instrutivo, o do literal numérico: dígitos, opcionalmente precedidos de sinal de menos e opcionalmente seguidos de separador decimal com mais dígitos. Aceitar 42, -7, -0.25; rejeitar a cadeia vazia, o sinal sozinho, a iniciada pelo separador, a terminada nele e a que tem dois.
flowchart LR
INI["início"]
Q0["q0<br/>não li nada"]
Q1["q1<br/>gastei o sinal,<br/>nenhum dígito ainda"]
Q2(["q2 final<br/>parte inteira"])
Q3["q3<br/>gastei o separador,<br/>nenhum dígito depois"]
Q4(["q4 final<br/>parte fracionária"])
INI --> Q0
Q0 -->|"-"| Q1
Q0 -->|"dígito"| Q2
Q1 -->|"dígito"| Q2
Q2 -->|"dígito"| Q2
Q2 -->|"."| Q3
Q3 -->|"dígito"| Q4
Q4 -->|"dígito"| Q4
O ponto está nos dois estados não finais intermediários, que existem por uma razão só: exigir que venha pelo menos mais um dígito. A tentação é economizar mandando o sinal direto para a parte inteira; o desenho fica com três estados, parece elegante, e aí o sinal sozinho passa a ser aceito. Generalizando: toda construção opcional que exige “pelo menos um” de alguma coisa pede um estado não final entre o gatilho e a repetição. Compare com o identificador, de expressão regular comparável e autômato de dois estados: a dificuldade não se mede pelo tamanho da descrição, e sim por quantas vezes a decisão depende do que já foi lido.
| Erro de projeto | Como se manifesta | Como se pega |
|---|---|---|
| Estado final prematuro | aceita construção incompleta | lista de rejeições escrita antes |
| Inicial mal marcado quanto à cadeia vazia | erra numa cadeia só, a que ninguém testa | conferir se a linguagem contém \varepsilon |
| Transição esquecida | rejeita silenciosamente cadeias válidas | conferência de contagem das células |
| Retorno indevido ao inicial | funciona na maioria das entradas | exemplos com ocorrência parcial do padrão |
| Estado supérfluo | não é defeito de correção, só de economia | corrigido pela minimização |
1.7 Da definição à estrutura de dados
A quíntupla é objeto matemático; o programa precisa de tipos, campos e laços. São quatro decisões, e gasto-as agora, com autômatos de cinco estados, porque são caras de rever depois.
flowchart TB
DEF["a quíntupla da definição"]
IDX["estados como índices inteiros<br/>num vetor, nunca referências"]
SIM["símbolo em tipo sem sinal<br/>convertido na fronteira da leitura"]
ESP["transições esparsas por estado<br/>dentro do compilador"]
LAC["reconhecimento em laço<br/>a indução desenrolada"]
GAN["copiar, comparar, serializar<br/>e usar conjuntos de estados<br/>como chave fica barato"]
SEG["byte alto não vira índice negativo"]
ALG["determinização e minimização<br/>percorrem o que existe"]
PIL["nenhum estouro de pilha<br/>em arquivo grande"]
DEF --> IDX --> GAN
DEF --> SIM --> SEG
DEF --> ESP --> ALG
DEF --> LAC --> PIL
A primeira é a mais consequente, e é onde a orientação a objetos sugere errado: cada estado como objeto e cada transição como referência de um objeto para outro. Parece limpo e range no terceiro algoritmo, porque um autômato é um grafo dirigido com ciclos. A alternativa é o estado como índice inteiro num vetor — comparar estados vira comparar inteiros, e os conjuntos de estados de que a determinização precisará serão conjuntos de inteiros. A segunda parece detalhe de linguagem e não é: o tipo de caractere natural de várias linguagens é assinado, e um byte acima de cento e vinte e sete vira negativo, que como chave desordena e como índice acessa fora dos limites. A terceira é estrutura esparsa dentro do compilador e matriz densa no artefato final, porque determinização e minimização percorrem as transições existentes. A quarta é implementar a função estendida como laço: a indução desenrolada, sem profundidade proporcional ao arquivo. Assim ficou a interface no meu caso conduzido, a Peneira:
using Estado = std::size_t;
using Simbolo = unsigned char;
inline constexpr Estado kSemEstado = static_cast<Estado>(-1);
class Afd {
public:
Estado novoEstado(bool final);
void adicionarTransicao(Estado de, Simbolo simbolo, Estado para);
Estado transicao(Estado de, Simbolo simbolo) const;
Estado deltaEstendido(Estado de, const Cadeia& s) const;
bool aceita(const Cadeia& s) const;
Afd completado() const;
private:
std::vector<std::map<Simbolo, Estado>> transicoes_;
};O valor sentinela de “não há estado” é a tradução direta do estado morto absorvente, e separar a consulta do estado alcançado do teste de finalidade preserva a distinção entre os dois modos de rejeição. Com essa estrutura projetei à mão os autômatos das categorias numérica e de identificador do módulo anterior e rodei-os contra os conjuntos de aceitação e de rejeição que tinham ficado lá como promessa, sem divergência: o que era contrato virou teste executável. Implemente também, ao lado da função que aceita ou rejeita, a que devolve a sequência de configurações instantâneas — mostra em que símbolo a computação saiu do trilho.
1.8 Síntese
A restrição definidora da quíntupla não é ter memória limitada, é tê-la limitada por uma constante fixada antes de ver a entrada. O comportamento vem em duas camadas, a configuração instantânea e o passo, sobre as quais se define por indução a função estendida, com a qual a aceitação cabe numa linha. As duas representações se dividem por função — o diagrama serve ao projeto, a tabela serve à execução —, e toda transição ausente equivale a uma transição para o estado morto. Volto ao incômodo da abertura: queríamos decidir pertinência para cadeias de qualquer comprimento, e agora temos uma máquina finita que representa um conjunto infinito e responde em tempo proporcional ao tamanho da cadeia. O preço foi construir os autômatos à mão, e no módulo seguinte ele deixa de ser pago — o autômato passa a ser produzido por algoritmo a partir da expressão regular, e o trabalho manual que você fez aqui ganha o papel de gabarito.