flowchart LR
A["conjunto atual<br/>{0, 1, 2}"] -->|"lê a"| B["mover por a<br/>{0}"]
B --> C["fecho vazio<br/>{0, 1, 2}"]
C -->|"lê b"| D["mover por b<br/>{3}"]
D --> E["fecho vazio<br/>{3}"]
E --> F{"contém<br/>estado final?"}
F -->|sim| G["aceita"]
F -->|não| H["rejeita"]
1 Módulo 05: Determinização e Minimização
Bem-vindo ao módulo que fecha o motor de reconhecimento. No módulo anterior deixei uma pergunta no ar de propósito, e ela é a razão de ser deste. Ao final desta leitura você vai saber transformar qualquer autômato não determinístico em um determinístico equivalente, encolher o resultado até o menor possível e — este é o prêmio — provar que duas especificações diferentes descrevem exatamente a mesma linguagem. Não por amostragem: por procedimento que responde certo, sempre.
1.1 O problema: a máquina que adivinha
Retomo a cena. Uma máquina não determinística faz coisas que parecem trapaça: diante de uma bifurcação, toma os dois caminhos ao mesmo tempo; diante de uma transição vazia, muda de estado sem consumir nada; e aceita a cadeia se algum caminho terminar em estado final — pode errar em todos os ramos menos um e ainda assim acertar. A pergunta que ficou é se essa liberdade aumenta o poder de reconhecimento.
Quando faço essa pergunta em sala a turma se divide, e a divisão é saudável. Só que quem aposta no “não” tem a seu favor um detalhe incômodo: a simulação que nós mesmos implementamos, aquela que carrega um conjunto de estados e o atualiza a cada símbolo, é um procedimento perfeitamente determinístico. Não há escolha nenhuma nela — e olha só como a demonstração cai no colo: se a simulação é determinística, então ela é um autômato determinístico, cujos estados são os conjuntos de estados do original.
Essa é a ideia de Michael Rabin e Dana Scott, publicada em 1959 no trabalho pelo qual os dois receberam o Prêmio Turing em 1976.
Pare e pense. Determinização e minimização parecem duas etapas do mesmo serviço de faxina. Não são. Uma apenas reorganiza informação, antecipando um cálculo; a outra descarta informação, fundindo o que ninguém consegue distinguir. Qual é qual? Confundir as duas é o erro conceitual mais comum deste assunto.
Este capítulo é o único do livro que depende fortemente do imediatamente anterior, e vale registrar o que ele pressupõe para que você possa voltar atrás se algo estiver frouxo.
Pressuponho a definição de autômato finito não determinístico com transições vazias e, sobretudo, as duas operações auxiliares que a acompanham: o fecho vazio de um conjunto de estados e o movimento de um conjunto por um símbolo. As duas foram escritas no capítulo anterior como funções independentes, e não enterradas dentro da rotina de simulação, precisamente porque este capítulo as consome sem alteração. Se, no seu próprio código, elas ficaram embutidas na simulação, extraia-as antes de continuar — o algoritmo desta seção se escreve em vinte linhas quando elas existem e em uma bagunça quando não existem.
Pressuponho também a construção de Thompson e o hábito de olhar para os autômatos que ela produz, porque a motivação inteira da minimização vem do tamanho deles. E pressuponho a representação de autômato adotada desde o capítulo sobre autômatos determinísticos: estados como índices inteiros em um vetor, nunca como ponteiros, e transições como pares de estado e símbolo levando a um estado. Essa escolha, que lá foi justificada pela facilidade de copiar e comparar, é o que torna possível representar um estado do autômato determinizado por um conjunto de índices e usar esse conjunto como chave de um dicionário. Com ponteiros, a mesma ideia exigiria uma disciplina de identidade que não vale o trabalho.
Do lado matemático, pressuponho relações de equivalência, classes de equivalência e conjunto quociente, além de percursos em largura e em profundidade sobre grafos. Nada além disso é necessário: a demonstração de unicidade deste capítulo é conduzida do início, e o argumento de contagem que estabelece o pior caso exponencial usa apenas o princípio de que cadeias com continuações distintas exigem estados distintos.
1.2 A construção de subconjuntos
Fixo a notação. Um autômato finito não determinístico com transições vazias é a quíntupla N = (Q, \Sigma, \delta, q_0, F), em que \delta leva um par de estado e símbolo — ou estado e transição vazia — em um conjunto de estados; o determinístico D = (Q', \Sigma, \Delta, s_0, F') tem \Delta devolvendo um único estado.
Duas operações fazem o trabalho. O fecho vazio de S, escrito E(S), é o menor conjunto que contém S e é fechado sob transições vazias: são os estados alcançáveis a partir de S sem consumir símbolo algum, incluindo os próprios estados de S — a inclusão corresponde ao caminho de comprimento zero, e esquecê-la é erro de estreia. O movimento de S por um símbolo a é a união dos destinos de a a partir de cada estado de S:
\mathrm{mover}(S, a) = \bigcup_{p \in S} \delta(p, a).
Com as duas no lugar, o determinístico correspondente cabe em três linhas. Seus estados são subconjuntos de Q; o inicial é E(\{q_0\}); um conjunto é final quando toca algum estado final do original; e a transição é \Delta(S, a) = E(\mathrm{mover}(S, a)).
Repara em três detalhes, porque cada um corresponde a um erro que eu vejo todo semestre. Primeiro, a ordem das operações: move-se antes e fecha-se depois. Quem inverte produz um autômato que rejeita cadeias legítimas, e o defeito é silencioso — só aparece em expressões com fecho ou opcional no meio, que são justamente as que qualquer especificação léxica usa. Segundo, o estado inicial é o fecho de q_0, não q_0 sozinho. Terceiro, o critério de finalidade exige pelo menos um estado final dentro do conjunto, e não todos.
Tomada ao pé da letra, essa definição manda construir um autômato com 2^{|Q|} estados, número sem sentido físico já para um autômato de Thompson de trezentos estados. Ninguém faz isso: a construção praticada gera apenas os subconjuntos alcançáveis a partir do inicial.
flowchart TD
I["conjunto inicial:<br/>fecho vazio do estado inicial"] --> Q["entra na fila<br/>e no dicionário"]
Q --> L{"fila vazia?"}
L -->|sim| F["autômato determinístico pronto"]
L -->|não| R["retira um conjunto S"]
R --> M["para cada símbolo a:<br/>primeiro mover por a,<br/>depois fechar sobre transições vazias"]
M --> D{"o conjunto destino<br/>já está no dicionário?"}
D -->|sim| U["reaproveita o estado existente"]
D -->|não| N["cria estado novo<br/>e enfileira o conjunto"]
U --> L
N --> L
O dicionário de conjuntos é a peça que faz tudo funcionar
É ele que garante que dois caminhos diferentes chegando ao mesmo conjunto de estados reutilizem o mesmo estado em vez de duplicá-lo. Sem essa reutilização, a construção geraria uma árvore infinita em qualquer autômato com ciclo. Com ela, a convergência de caminhos é detectada de graça — e é essa convergência que explica por que o resultado prático fica tão longe do pior caso teórico.
Falta decidir o que fazer quando o movimento resulta vazio. As duas convenções abaixo reconhecem a mesma linguagem; o que não se pode é oscilar entre elas.
A definição formal exige transição total, o que obriga a criar um estado de erro explícito, não final, do qual todas as transições voltam para ele mesmo. É a forma canônica, exigida pela minimização por refinamento, cuja assinatura de estado precisa de destino definido para cada símbolo.
A transição simplesmente não é declarada, e a ausência já significa rejeição. Num autômato léxico, com alfabeto de duzentos e cinquenta e seis símbolos e estados que definem transição para uma dúzia deles, declarar o resto explicitamente multiplica o tamanho da tabela para representar o que a ausência já representa.
1.3 Dois traçados à mão, e a demonstração
Nada substitui fazer o algoritmo à mão uma vez. Tome o autômato sobre \Sigma = \{a, b\} com estados 0, 1, 2 e 3, inicial 0 e único final 3, com duas transições vazias saindo de 0 (para 1 e para 2), uma por a de 1 de volta para 0 e uma por b de 2 para 3. A linguagem é a^*b.
O estado inicial do determinístico é E(\{0\}) = \{0,1,2\}, que chamo de A. Por a, mover dá \{0\}, e o fecho devolve o próprio A. Por b, mover dá \{3\}, cujo fecho é \{3\}, conjunto novo que chamo de B, de onde não sai nada. A fila esvazia: quatro estados viraram dois, e as transições vazias sumiram, absorvidas na definição dos conjuntos.
Seria desonesto parar aqui, porque esse exemplo encolheu. Tome agora o autômato que reconhece as cadeias cujo penúltimo símbolo é a: um q_0 que lê qualquer símbolo e permanece em si mesmo e que, ao ler um a, também pode ir para q_1 — é aqui que ele adivinha; um q_1 que lê qualquer coisa e vai para q_2; e q_2 final.
| Estado | Conjunto | por a | por b | final |
|---|---|---|---|---|
| A | \{q_0\} | B | A | não |
| B | \{q_0,q_1\} | C | D | não |
| C | \{q_0,q_1,q_2\} | C | D | sim |
| D | \{q_0,q_2\} | B | A | sim |
flowchart LR
subgraph encolheu["quatro estados viram dois"]
direction LR
A0(("A = {0,1,2}"))
A1(("B = {3}<br/>final"))
A0 -->|a| A0
A0 -->|b| A1
end
subgraph cresceu["três estados viram quatro"]
direction LR
B0(("A"))
B1(("B"))
B2(("C<br/>final"))
B3(("D<br/>final"))
B0 -->|a| B1
B0 -->|b| B0
B1 -->|a| B2
B1 -->|b| B3
B2 -->|a| B2
B2 -->|b| B3
B3 -->|a| B1
B3 -->|b| B0
end
Vale ler o que cada estado está lembrando, porque é isso que torna o algoritmo intuitivo em vez de mecânico: os quatro estados correspondem às quatro combinações possíveis dos dois últimos símbolos lidos. A adivinhação virou memória, e memória custa estados.
Convencer não é demonstrar. A prova é por indução sobre o comprimento da cadeia e mostra que o estado em que o determinístico se encontra depois de ler w é, como conjunto, exatamente o conjunto de estados em que o não determinístico poderia estar depois de ler w. Note o que ela não usa: nada sobre a forma do autômato de partida. Por isso o resultado é sobre classes de linguagens, e não sobre uma técnica de implementação.
1.4 O preço da determinização
A definição dá de graça um limite superior: se o autômato de partida tem n estados, o determinizado tem no máximo 2^n estados alcançáveis, porque os estados do resultado são subconjuntos de um conjunto de n elementos. O limite é tranquilizador por ser finito — a determinização sempre termina, e é isso que garante que a fila esvazia — e alarmante porque 2^n cresce depressa: com n = 40 já passa de um trilhão, e um autômato de Thompson com quarenta estados é pequeno.
Resta saber se o limite é apertado ou estimativa preguiçosa, e a resposta é desconfortável. Para cada inteiro k \ge 1, considere a linguagem L_k das cadeias sobre \{a,b\} cujo k-ésimo símbolo, contado a partir do fim, é a. Um autômato não determinístico a reconhece com k+1 estados, generalizando o traçado do penúltimo símbolo.
flowchart LR
Q0(("q0<br/>inicial")) -->|"a, b"| Q0
Q0 -->|"a: adivinha que este<br/>é o símbolo de interesse"| Q1(("q1"))
Q1 -->|"a, b"| Q2(("q2"))
Q2 -->|"a, b"| QM(("cadeia de<br/>k-1 estados"))
QM -->|"a, b"| QF(("qk<br/>final"))
E todo autômato determinístico que reconhece L_k tem pelo menos 2^k estados. Considere as 2^k cadeias de comprimento exatamente k: duas distintas levam necessariamente a estados distintos. Sejam u \neq v diferindo primeiro na posição i, com u_i = a e v_i = b, e anexe a ambas uma cadeia z de i-1 símbolos quaisquer. O k-ésimo símbolo contado do fim cai exatamente na posição i, logo uz \in L_k e vz \notin L_k; se as duas levassem ao mesmo estado, o autômato daria o mesmo veredicto sobre ambas.
Este é o ponto que eu quero que fique. O crescimento exponencial não é defeito do algoritmo de Rabin e Scott: é propriedade da diferença de expressividade entre os dois formalismos, e qualquer construção correta pagaria o mesmo preço. E repara no que a minimização vai poder fazer aqui: nada, porque acabamos de mostrar que todos aqueles estados são dois a dois distinguíveis.
Então por que a determinização é técnica padrão em compiladores, aplicada sobre especificações com centenas de estados? Porque a explosão exige manter vivas simultaneamente muitas hipóteses não convergentes, e as expressões que a gente escreve de verdade não têm essa característica: nelas os caminhos paralelos gerados por Thompson convergem depressa, porque os fragmentos alternativos de uma união desembocam no mesmo ponto de junção. A classe das letras minúsculas, por exemplo, vira cerca de cem estados para dizer “uma letra qualquer” — só que, depois de ler uma letra, o conjunto de estados alcançados é o mesmo, seja qual for a letra lida, e a construção descobre isso sozinha ao consultar o dicionário. Não confunda, porém, “raramente acontece” com “não acontece”: se o seu projeto aceitar expressões escritas por terceiros, vale impor um teto de estados com mensagem clara.
Um hábito que vale para muito além deste módulo. Meça e registre o número de estados nas três etapas — não determinístico, determinizado e mínimo — para cada categoria da sua especificação. São três números coletados em duas linhas de código, e eles viram um teste de regressão barato: se uma categoria pula de cinco para dezessete estados depois de uma alteração aparentemente inofensiva, alguma coisa mudou na linguagem reconhecida.
1.5 Estados supérfluos: os órfãos e os mortos
Antes de minimizar, precisamos limpar um desperdício que não tem nada a ver com indistinguibilidade e que atrapalha o algoritmo se ficar para depois. Um estado é alcançável quando existe alguma cadeia que leva o autômato até ele a partir do inicial; um inalcançável não participa de computação nenhuma, e por isso removê-lo não altera a linguagem. Identificá-los é um percurso a partir do inicial marcando o que se visita, e o que sobra sem marca vai embora. O único trabalho real está em renumerar os estados restantes, e é aí que nasce o defeito mais comum: renumerar e esquecer de traduzir os índices que aparecem nos destinos das transições ou no registro de quais estados são finais.
Um estado é morto quando nenhum estado final é alcançável a partir dele: uma vez dentro, a cadeia será rejeitada aconteça o que acontecer com o resto da entrada. Todos os mortos são indistinguíveis entre si, e a minimização os funde num só — na forma completa o mínimo tem esse estado, na parcial ele é implícito e o mínimo tem um estado a menos.
flowchart LR
S(("inicial")) -->|a| P(("p"))
S -->|b| S
P -->|b| F(("f<br/>final"))
P -->|a| M(("m<br/>morto"))
M -->|"a, b"| M
F -->|"a, b"| F
O(("o<br/>inalcançável")) -->|a| F
Uma observação sobre ordem, fácil de enunciar e fácil de esquecer: a remoção de inalcançáveis vem antes do refinamento de partições, nunca depois. Um órfão participa do refinamento como qualquer outro estado e não pode ser fundido com ninguém só por não ser alcançado, já que o critério de fusão é comportamental. Ele sobrevive sozinho num bloco, infla a contagem e pode até induzir separações entre estados que, no autômato limpo, seriam equivalentes. O resultado continua reconhecendo a linguagem certa e deixa de ser mínimo — correto o bastante para passar nos testes de comportamento e errado o bastante para quebrar a unicidade, que é justamente o que a minimização existe para entregar.
1.6 Quando dois estados são, na prática, o mesmo
Chegamos ao ponto conceitualmente mais difícil, e quero começar pela pergunta: quando é que dois estados podem ser tratados como um só?
A resposta ingênua olha para dentro do estado — para as transições que saem dele, para os símbolos que ele aceita, para a posição no desenho. Todas erradas do mesmo jeito: elas olham para a estrutura quando a pergunta é sobre comportamento. O critério correto é este: dois estados são intercambiáveis quando, colocando a máquina em um ou no outro e alimentando-a com qualquer continuação possível, o veredicto final é o mesmo. Formalmente, p e q são indistinguíveis quando, para toda cadeia w, vale \hat\Delta(p,w) \in F se e somente se \hat\Delta(q,w) \in F; qualquer w que testemunhe a diferença é uma cadeia distinguidora. O quantificador inclui a cadeia vazia, e tomá-la já diz que um estado final nunca é indistinguível de um não final — por onde o algoritmo começa.
flowchart LR
Z(("0<br/>nenhum a")) -->|a| U(("1<br/>um a"))
Z -->|b| Z
U -->|a| D(("2<br/>dois a"))
U -->|b| U
D -->|a| T(("3<br/>final"))
D -->|b| D
T -->|"a, b"| T
Preciso desmontar a intuição errada mais comum, porque ela é sedutora e sobrevive a explicações genéricas: a de que dois estados com as mesmas transições de saída, rotuladas pelas mesmas letras, são equivalentes. Olha o diagrama. Os estados 0 e 1 têm transições pelos mesmos dois símbolos e ambos são não finais — e são distinguíveis, porque a cadeia aa leva 1 ao estado final e leva 0 ao estado 2, que não é final.
Estrutura não é comportamento, nos dois sentidos. Aparências idênticas com comportamentos diferentes, como acabamos de ver; e também aparências diferentes com comportamentos idênticos, porque dois estados cujas transições apontam para estados diferentes são indistinguíveis desde que esses destinos o sejam entre si. É essa circularidade que impede uma verificação local e obriga a um cálculo de ponto fixo.
A circularidade se resolve estratificando a relação por comprimento, e a estratificação é literalmente o algoritmo da próxima seção. Dizemos que p e q são k-indistinguíveis quando nenhuma cadeia de comprimento até k os separa. O nível zero separa apenas finais de não finais, e vale a caracterização recursiva que faz tudo funcionar: p e q são (k{+}1)-indistinguíveis exatamente quando são k-indistinguíveis e, para todo símbolo a, os destinos \Delta(p,a) e \Delta(q,a) também são k-indistinguíveis. Basta olhar um passo à frente, desde que se saiba a resposta para k. E se um nível coincide com o anterior, todos os seguintes coincidem, porque cada relação é calculada exclusivamente a partir da anterior — o processo estabiliza na indistinguibilidade verdadeira.
Como a relação é reflexiva, simétrica e transitiva, ela particiona os estados em classes. O autômato quociente toma as classes como estados, a classe do inicial como inicial, as classes contidas em F como finais, e define a transição de uma classe escolhendo um representante — escolha que não importa, porque se dois estados são indistinguíveis seus destinos por qualquer símbolo também são. É a compatibilidade com as transições, e é o que faz o quociente existir.
1.7 Minimização por refinamento de partições
Definimos o resultado; falta calculá-lo. O cálculo é o algoritmo publicado por Edward Moore em 1956, num trabalho sobre o que se descobre de uma máquina sequencial apenas experimentando com ela — nada coincidente, já que estados indistinguíveis são os que nenhum experimento separa.
O algoritmo mantém uma partição e a refina até estabilizar, começando por dois blocos, finais e não finais. A cada rodada, calcula-se para cada estado a sua assinatura com respeito à partição corrente: a lista, ordenada pelos símbolos do alfabeto, dos blocos a que levam as suas transições. Dois estados do mesmo bloco com assinaturas diferentes são distinguíveis, e o bloco se subdivide em tantos sub-blocos quantos forem os valores distintos de assinatura. Quando uma rodada inteira não produz subdivisão, chegamos ao ponto fixo, e cada bloco vira um estado do mínimo.
A assinatura é de blocos de destino, não de símbolos. O erro que mais vejo é montá-la com os símbolos para os quais o estado tem transição definida, ignorando para onde ela vai. A partição sai grossa demais, o algoritmo termina cedo e o autômato reconhece a linguagem errada — defeito silencioso, porque a linguagem errada costuma ser um superconjunto que passa em muitos testes.
Vamos ver o algoritmo trabalhando. Tome o autômato sobre \{a,b\} com cinco estados, que vou chamar de 0, 1, 2, 2' e 3, inicial 0 e único final 3. De 0, por a para 1 e por b para si mesmo; de 1, por a para 2 e por b para si mesmo; de 2, por a para 3 e por b para 2'; de 2', por a para 3 e por b para 2; de 3, por qualquer símbolo para si mesmo. A linguagem é a das cadeias com pelo menos três a, e os estados 2 e 2' significam a mesma coisa: “dois a lidos”.
flowchart TD
R["rodada inicial<br/>bloco dos não finais {0, 1, 2, 2'}<br/>bloco dos finais {3}"]
A["primeira rodada<br/>{0, 1} · {2, 2'} · {3}"]
B["segunda rodada<br/>{0} · {1} · {2, 2'} · {3}"]
C["terceira rodada<br/>nenhuma separação nova:<br/>ponto fixo alcançado"]
R -->|"separa quem alcança o final em um passo"| A
A -->|"separa quem alcança o final em dois passos"| B
B --> C
Na primeira rodada, 0 e 1 têm assinatura formada por dois destinos no bloco dos não finais, enquanto 2 e 2' levam por a ao bloco final, e o bloco grande se parte em dois. Na segunda, 0 leva por a a 1 e 1 leva por a a 2, que agora estão em blocos diferentes, e os dois se separam. Este é o momento instrutivo: 2 e 2' continuam juntos, embora suas transições por b vão para estados diferentes, porque os dois destinos estão no mesmo bloco. Na terceira rodada nada se separa, e o ponto fixo chega com quatro estados.
Repare que o algoritmo redescobriu uma distinção que existia por razões semânticas — quantos a já foram vistos — sem saber nada sobre contagem.
Refinamento por rodadas. Cada rodada monta a assinatura dos n estados, com uma entrada por símbolo usado, e há no máximo n rodadas: tempo da ordem de k\,n^2 com k símbolos. Duas vantagens didáticas concretas: a partição a cada rodada é observável e corresponde à k-indistinguibilidade, e a implementação cabe em poucas dezenas de linhas.
Mesmo problema em tempo da ordem de k\,n \log n. Em vez de recalcular tudo, mantém uma fila de blocos ainda não usados como separadores e examina apenas os estados com transição entrando no separador; ao dividir um bloco, enfileira o menor pedaço, o que limita a \log n as separações de que cada estado participa. Compensa com milhares de estados.
Obtém o mínimo revertendo e determinizando duas vezes. Dispensa partições e paga um pior caso exponencial. Vale pela lição de que a determinização do autômato reverso já carrega a informação de indistinguibilidade.
1.8 Unicidade, e o que ela decide
Sabemos calcular um autômato equivalente com menos estados; falta saber se é o menor e se é único. Dois autômatos são isomorfos quando existe uma bijeção entre seus estados que preserva o inicial, os finais e as transições — “o mesmo autômato com os estados chamados por outros nomes”. E o teorema diz: entre todos os autômatos determinísticos completos que reconhecem uma linguagem regular, existe um com número mínimo de estados, único a menos de isomorfismo, e ele é o quociente de qualquer autômato completo e acessível que reconheça a linguagem.
O argumento é direto. Tome A e B reduzidos, acessíveis e completos, reconhecendo a mesma linguagem, e associe ao estado que A alcança lendo w o estado que B alcança lendo w. Se duas cadeias levam ao mesmo estado em A, elas têm as mesmas continuações aceitas; logo os estados alcançados em B são indistinguíveis e, como B é reduzido, são o mesmo estado. A correspondência está bem definida, o argumento simétrico dá a injetividade, e o resto sai da construção.
As hipóteses não são decorativas. O teorema exige acessibilidade: dois autômatos podem reconhecer a mesma linguagem, ser reduzidos e ter tamanhos diferentes se um deles carregar estados órfãos. E exige convenção fixa quanto à totalidade: o mínimo completo tem o estado morto, o mínimo parcial não tem, e comparar um de cada tipo produz uma diferença de exatamente um estado que não significa coisa alguma.
Um objeto mínimo e único é uma forma canônica, e é aqui que o teorema vira ferramenta. O procedimento é: remova inalcançáveis, minimize e numere os estados canonicamente, por um percurso em largura a partir do inicial visitando os símbolos em ordem crescente. Dois autômatos isomorfos produzem numerações idênticas, porque o percurso é determinado pela estrutura e pela ordem dos símbolos, não pelos nomes originais.
flowchart LR
E1["primeira expressão"] --> N1["autômato não determinístico"] --> D1["determinizar"] --> A1["remover inalcançáveis"] --> M1["minimizar"] --> C1["numeração canônica"]
E2["segunda expressão"] --> N2["autômato não determinístico"] --> D2["determinizar"] --> A2["remover inalcançáveis"] --> M2["minimizar"] --> C2["numeração canônica"]
C1 --> T{"finalidade e transições<br/>casam estado a estado?"}
C2 --> T
T -->|sim| S["as duas expressões<br/>denotam a mesma linguagem"]
T -->|não| X["existe cadeia que<br/>uma aceita e a outra não"]
Compare com o que a gente tinha antes. Sem a minimização, comparar duas expressões só era possível gerando as cadeias que cada uma denota até um comprimento escolhido — evidência, e evidência frágil, porque duas expressões podem coincidir em todas as cadeias de comprimento até dez e divergir na primeira de comprimento onze. Agora existe o procedimento de verdade, e ele vale para qualquer comprimento, porque a unicidade transformou “comparar conjuntos infinitos” em “comparar dois objetos finitos”. Um aviso: não aceite a igualdade do número de estados como evidência, porque dois autômatos mínimos do mesmo tamanho podem reconhecer linguagens completamente diferentes. É para isso que a numeração canônica existe.
Outras decisões vêm quase de graça: decidir se uma linguagem regular é vazia é verificar se algum final é alcançável, e decidir se é infinita é procurar um ciclo num caminho do inicial a algum final. E há uma consequência de projeto imediata — duas categorias léxicas cujas especificações se sobrepõem são fonte clássica de defeito sutil, e com as ferramentas deste módulo a sobreposição vira pergunta respondível antes de qualquer entrada existir: componha os dois autômatos por interseção e verifique se o resultado reconhece a linguagem vazia.
1.9 Ver para depurar
Até aqui, os autômatos do projeto eram desenhados por pessoas, e conferir um deles lendo a tabela era chato mas viável. Isso acabou: a partir da determinização eles passam a ser produzidos por algoritmo, com dezenas ou centenas de estados, e conferir a tabela vira o tipo de tarefa em que a atenção humana falha em silêncio — você lê, tudo parece plausível, e o defeito continua lá. O olho, por outro lado, é excelente em grafos: diante do desenho, você percebe num segundo que existe uma ilha desconectada, que um estado final não tem entrada, que um rótulo tem uma letra a mais.
O formato consagrado para descrever grafos em texto é a linguagem DOT, da família Graphviz: é texto simples, legível mesmo sem a ferramenta de desenho instalada, e delega a um programa maduro o posicionamento dos nós. Siga as três convenções dos livros: círculo duplo para os finais, uma seta vinda de um nó invisível para marcar o inicial, e um rótulo com o nome da categoria e a contagem de estados.
Um detalhe separa o diagrama útil do borrão: um estado de autômato léxico costuma ter transição definida para dezenas de símbolos com o mesmo destino, e uma aresta por símbolo produz um emaranhado ilegível. Agrupe os símbolos contíguos que levam ao mesmo destino numa única aresta rotulada com a faixa.
flowchart TD
A["autômato produzido por algoritmo"] --> B["cadeias de teste<br/>confere comportamento<br/>nos casos que alguém previu"]
A --> C["teste de isomorfismo<br/>confere estrutura<br/>de forma conclusiva"]
A --> D["diagrama<br/>expõe tudo o que o autômato faz,<br/>inclusive o que ninguém perguntou"]
B --> E["defeito encontrado cedo"]
C --> E
D --> E
Uma ressalva honesta: o diagrama é uma visão da estrutura de dados, não uma verificação independente dela — se a expressão foi mal interpretada, ele exibe com clareza o autômato errado. Mas é por exibir tudo que ele pega defeitos que nenhuma bateria de testes pega, já que cadeias de teste só verificam o que alguém pensou em testar.
1.10 O motor de autômatos do caso conduzido
Tudo converge para uma peça só: uma função que recebe uma expressão regular e devolve o autômato finito determinístico mínimo que reconhece a linguagem denotada por ela. Os módulos anteriores construíram as duas primeiras etapas dessa cadeia; este fecha as duas restantes. E esse motor não é utilitário auxiliar do compilador: ele é usado duas vezes — uma pelo compilador, para reconhecer as categorias léxicas da linguagem que estamos construindo, e outra pelo programa compilado, para reconhecer os padrões que o usuário declarou. As duas consomem exatamente o mesmo código.
1.10.1 8.1 A determinização, com o fecho vazio reaproveitado
A implementação da construção de subconjuntos é a tradução literal da Definição 1.3 com o refinamento sob demanda da seção 1.3. A interface declara três funções: a determinização propriamente dita, a remoção de estados inalcançáveis e a contagem de inalcançáveis, que serve aos relatórios.
05_determinizacao.h
#ifndef PENEIRA_05_DETERMINIZACAO_H
#define PENEIRA_05_DETERMINIZACAO_H
#include <cstddef>
#include <string>
#include "03_afd.h"
#include "04_afn.h"
namespace peneira {
// Construção de subconjuntos: converte o autômato não determinístico no
// determinístico equivalente.
//
// A ideia inteira cabe numa frase: cada estado do autômato resultante é um
// CONJUNTO de estados do original. É exatamente o conjunto que a simulação do
// módulo 4 carregava durante a execução — a diferença é que aqui o cálculo é
// feito uma vez, ainda na construção, e não a cada entrada processada.
Afd determinizar(const Afn& afn, std::string nome);
// Remove os estados que não são alcançáveis a partir do inicial. A construção
// de subconjuntos já produz só estados alcançáveis, mas um autômato escrito à
// mão pode ter estados órfãos, e a minimização precisa deles fora antes de
// começar.
Afd removerInalcancaveis(const Afd& original);
// Quantos estados do autômato dado são inalcançáveis. Usado nos relatórios.
std::size_t contarInalcancaveis(const Afd& original);
} // namespace peneira
#endif // PENEIRA_05_DETERMINIZACAO_H
O corpo da determinização é curto porque as duas operações caras já existiam.
05_determinizacao.cpp
#include "05_determinizacao.h"
#include <map>
#include <set>
#include <utility>
#include <vector>
namespace peneira {
namespace {
// Percorre o autômato a partir do inicial e devolve os estados alcançados.
std::set<Estado> alcancaveis(const Afd& a) {
std::set<Estado> vistos;
if (a.inicial() == kSemEstado) {
return vistos;
}
const std::vector<Simbolo> alfabeto = a.simbolosUsados();
std::vector<Estado> pilha{a.inicial()};
vistos.insert(a.inicial());
while (!pilha.empty()) {
const Estado atual = pilha.back();
pilha.pop_back();
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(atual, s);
if (destino != kSemEstado && vistos.insert(destino).second) {
pilha.push_back(destino);
}
}
}
return vistos;
}
} // namespace
Afd determinizar(const Afn& afn, std::string nome) {
Afd resultado(std::move(nome));
if (afn.inicial() == kSemEstado) {
return resultado;
}
const std::vector<Simbolo> alfabeto = afn.simbolosUsados();
// O mapa é a peça central: leva cada conjunto de estados do original ao
// índice do estado que o representa no resultado. É ele que faz dois
// caminhos diferentes que chegam ao mesmo conjunto reutilizarem o mesmo
// estado, em vez de duplicá-lo — e é por isso que o resultado costuma ser
// muito menor que o pior caso teórico.
std::map<std::set<Estado>, Estado> conhecidos;
std::vector<std::set<Estado>> fila;
const std::set<Estado> inicial = afn.fechoVazio(std::set<Estado>{afn.inicial()});
conhecidos[inicial] = resultado.novoEstado(inicial.count(afn.final()) > 0);
resultado.definirInicial(conhecidos[inicial]);
fila.push_back(inicial);
for (std::size_t i = 0; i < fila.size(); ++i) {
const std::set<Estado> atual = fila[i];
const Estado origem = conhecidos[atual];
for (const Simbolo s : alfabeto) {
const std::set<Estado> destino =
afn.fechoVazio(afn.mover(atual, s));
// Conjunto vazio significa que não há para onde ir com este
// símbolo. Não criamos estado para ele: fica como transição
// indefinida, que é o estado de erro implícito da representação
// esparsa adotada no módulo 3.
if (destino.empty()) {
continue;
}
const auto it = conhecidos.find(destino);
Estado indice;
if (it == conhecidos.end()) {
indice = resultado.novoEstado(destino.count(afn.final()) > 0);
conhecidos[destino] = indice;
fila.push_back(destino);
} else {
indice = it->second;
}
resultado.adicionarTransicao(origem, s, indice);
}
}
return resultado;
}
std::size_t contarInalcancaveis(const Afd& original) {
return original.quantidadeDeEstados() - alcancaveis(original).size();
}
Afd removerInalcancaveis(const Afd& original) {
const std::set<Estado> vivos = alcancaveis(original);
Afd resultado(original.nome());
std::map<Estado, Estado> novoIndice;
for (const Estado e : vivos) {
novoIndice[e] = resultado.novoEstado(original.ehFinal(e));
}
if (novoIndice.count(original.inicial()) > 0) {
resultado.definirInicial(novoIndice[original.inicial()]);
}
const std::vector<Simbolo> alfabeto = original.simbolosUsados();
for (const Estado e : vivos) {
for (const Simbolo s : alfabeto) {
const Estado destino = original.transicao(e, s);
if (destino != kSemEstado && novoIndice.count(destino) > 0) {
resultado.adicionarTransicao(novoIndice[e], s,
novoIndice[destino]);
}
}
}
return resultado;
}
} // namespace peneira
Repare que o algoritmo reutiliza sem alteração o fecho vazio e o movimento por símbolo escritos no capítulo anterior. Isso não foi sorte: eles foram escritos naquele momento já com este uso em vista, o que é a razão pela qual insisti, lá, em torná-los públicos em vez de deixá-los escondidos dentro da rotina de simulação.
A peça central é o dicionário que leva cada conjunto de estados ao índice do estado que o representa. É ele que faz dois caminhos distintos que chegam ao mesmo conjunto reaproveitarem o mesmo estado, e é essa reutilização que explica, na prática, a distância entre o resultado observado e o pior caso do Teorema 2.1.
Duas decisões de representação foram tomadas de forma consciente e vale declará-las. Quando o conjunto destino é vazio, nenhum estado é criado e a transição fica indefinida — na representação esparsa adotada desde o capítulo sobre autômatos determinísticos, a ausência já significa rejeição. É a forma parcial da seção 3.2, e a conversão para a forma completa continua disponível quando algum algoritmo a exigir, que é exatamente o caso da minimização. E os conjuntos são representados como conjuntos ordenados de índices, o que os torna comparáveis e utilizáveis como chave sem código adicional.
Aviso
Onde é fácil errar aqui. Esquecer o fecho vazio depois do movimento. A sequência correta é mover por símbolo e então fechar sobre as transições vazias do resultado; quem fecha apenas no estado inicial produz um autômato que rejeita cadeias válidas, e o defeito só se manifesta em expressões com fecho ou opcional no meio — que são justamente as que qualquer especificação léxica usa.
1.10.2 8.2 A minimização por refinamento
A interface da minimização declara três funções, e a terceira é a que transforma o Teorema 6.1 em verificação executável.
05_minimizacao.h
#ifndef PENEIRA_05_MINIMIZACAO_H
#define PENEIRA_05_MINIMIZACAO_H
#include <string>
#include "03_afd.h"
namespace peneira {
// Minimização por refinamento de partições (algoritmo de Moore).
//
// A ideia: começar supondo que só existem duas classes de estados — finais e
// não finais — e ir separando sempre que dois estados da mesma classe levarem,
// com o mesmo símbolo, a classes diferentes. Quando nenhuma separação nova
// aparece, cada classe vira um estado do autômato mínimo.
//
// O resultado é ÚNICO a menos de renomeação dos estados, e é esse resultado
// que transforma a pergunta "estas duas especificações descrevem a mesma
// linguagem?" num procedimento mecânico: minimize as duas e compare.
Afd minimizar(const Afd& original, std::string nome);
// Registro passo a passo do refinamento: quais estados estavam juntos em cada
// rodada e o que provocou cada separação.
std::string tracarMinimizacao(const Afd& original);
// Compara dois autômatos por estrutura, ignorando os nomes dos estados.
// Numera os dois canonicamente por percurso em largura a partir do inicial,
// visitando os símbolos em ordem, e exige que a numeração resultante case.
//
// É com esta função que a unicidade do autômato mínimo deixa de ser um
// enunciado e vira verificação: dois autômatos mínimos da mesma linguagem
// precisam sair isomorfos, venham de onde vierem.
bool isomorfos(const Afd& a, const Afd& b);
} // namespace peneira
#endif // PENEIRA_05_MINIMIZACAO_H
05_minimizacao.cpp
#include "05_minimizacao.h"
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <utility>
#include <vector>
#include "05_determinizacao.h"
namespace peneira {
namespace {
// Calcula a partição estável dos estados. Devolve, para cada estado, o índice
// do bloco a que ele pertence.
std::vector<std::size_t> particionar(const Afd& a,
const std::vector<Simbolo>& alfabeto,
std::ostringstream* trilha) {
const std::size_t n = a.quantidadeDeEstados();
std::vector<std::size_t> bloco(n, 0);
// Partição inicial: finais de um lado, não finais do outro. Se todos os
// estados forem do mesmo tipo, já começamos com um bloco só.
for (std::size_t e = 0; e < n; ++e) {
bloco[e] = a.ehFinal(e) ? 1u : 0u;
}
std::size_t rodada = 0;
for (;;) {
if (trilha != nullptr) {
std::map<std::size_t, std::vector<Estado>> porBloco;
for (std::size_t e = 0; e < n; ++e) {
porBloco[bloco[e]].push_back(e);
}
*trilha << " rodada " << rodada << ": " << porBloco.size()
<< " bloco(s)\n";
for (const auto& par : porBloco) {
*trilha << " {";
for (std::size_t i = 0; i < par.second.size(); ++i) {
if (i > 0) *trilha << ", ";
*trilha << "q" << par.second[i];
}
*trilha << "}" << (a.ehFinal(par.second.front()) ? " final" : "")
<< '\n';
}
}
// A assinatura de um estado é o bloco dele mais o bloco de destino de
// cada símbolo. Dois estados no mesmo bloco com assinaturas diferentes
// são distinguíveis e precisam ser separados.
std::map<std::vector<long long>, std::size_t> novoIndice;
std::vector<std::size_t> novoBloco(n, 0);
for (std::size_t e = 0; e < n; ++e) {
std::vector<long long> assinatura;
assinatura.reserve(alfabeto.size() + 1);
assinatura.push_back(static_cast<long long>(bloco[e]));
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(e, s);
assinatura.push_back(
destino == kSemEstado
? -1
: static_cast<long long>(bloco[destino]));
}
const auto it = novoIndice.find(assinatura);
if (it == novoIndice.end()) {
const std::size_t indice = novoIndice.size();
novoIndice[assinatura] = indice;
novoBloco[e] = indice;
} else {
novoBloco[e] = it->second;
}
}
if (novoBloco == bloco) {
if (trilha != nullptr) {
*trilha << " nenhuma separacao nova: ponto fixo alcancado\n";
}
return bloco;
}
bloco = novoBloco;
++rodada;
}
}
// Um bloco é morto quando não tem estado final e todas as suas transições
// voltam para ele mesmo: entrar nele significa nunca mais aceitar.
bool blocoEhMorto(const Afd& a, const std::vector<std::size_t>& bloco,
std::size_t alvo, const std::vector<Simbolo>& alfabeto) {
bool temEstado = false;
for (std::size_t e = 0; e < a.quantidadeDeEstados(); ++e) {
if (bloco[e] != alvo) {
continue;
}
temEstado = true;
if (a.ehFinal(e)) {
return false;
}
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(e, s);
if (destino != kSemEstado && bloco[destino] != alvo) {
return false;
}
}
}
return temEstado;
}
} // namespace
Afd minimizar(const Afd& original, std::string nome) {
// Ordem obrigatória: primeiro tirar os inalcançáveis. Um estado que
// ninguém alcança pode ficar sozinho num bloco e inflar o resultado sem
// que isso signifique nada sobre a linguagem.
const Afd limpo = removerInalcancaveis(original);
const std::vector<Simbolo> alfabeto = limpo.simbolosUsados();
if (limpo.quantidadeDeEstados() == 0) {
return Afd(std::move(nome));
}
const std::vector<std::size_t> bloco =
particionar(limpo, alfabeto, nullptr);
std::size_t totalDeBlocos = 0;
for (const std::size_t b : bloco) {
totalDeBlocos = (b + 1 > totalDeBlocos) ? b + 1 : totalDeBlocos;
}
// O bloco morto é descartado: voltamos à representação esparsa do módulo 3,
// em que a transição ausente já significa rejeição. O autômato mínimo da
// teoria, com função total, é este mais o estado morto de volta — mesma
// linguagem, uma escolha de representação de diferença.
std::size_t blocoMorto = totalDeBlocos;
for (std::size_t b = 0; b < totalDeBlocos; ++b) {
if (blocoEhMorto(limpo, bloco, b, alfabeto)) {
blocoMorto = b;
break;
}
}
Afd resultado(std::move(nome));
std::map<std::size_t, Estado> indiceDoBloco;
for (std::size_t b = 0; b < totalDeBlocos; ++b) {
if (b == blocoMorto) {
continue;
}
bool final = false;
for (std::size_t e = 0; e < limpo.quantidadeDeEstados(); ++e) {
if (bloco[e] == b) {
final = limpo.ehFinal(e);
break;
}
}
indiceDoBloco[b] = resultado.novoEstado(final);
}
if (indiceDoBloco.count(bloco[limpo.inicial()]) > 0) {
resultado.definirInicial(indiceDoBloco[bloco[limpo.inicial()]]);
}
// Uma transição por bloco e símbolo: como todos os estados do bloco têm a
// mesma assinatura, basta consultar o primeiro deles.
std::set<std::size_t> jaEmitidos;
for (std::size_t e = 0; e < limpo.quantidadeDeEstados(); ++e) {
const std::size_t b = bloco[e];
if (b == blocoMorto || !jaEmitidos.insert(b).second) {
continue;
}
for (const Simbolo s : alfabeto) {
const Estado destino = limpo.transicao(e, s);
if (destino == kSemEstado) {
continue;
}
const std::size_t destinoBloco = bloco[destino];
if (destinoBloco == blocoMorto) {
continue;
}
resultado.adicionarTransicao(indiceDoBloco[b], s,
indiceDoBloco[destinoBloco]);
}
}
return resultado;
}
std::string tracarMinimizacao(const Afd& original) {
const Afd limpo = removerInalcancaveis(original);
std::ostringstream trilha;
trilha << "refinamento de particoes de " << original.nome() << " ("
<< limpo.quantidadeDeEstados() << " estados alcancaveis)\n";
if (limpo.quantidadeDeEstados() > 0) {
particionar(limpo, limpo.simbolosUsados(), &trilha);
}
return trilha.str();
}
bool isomorfos(const Afd& a, const Afd& b) {
if (a.quantidadeDeEstados() != b.quantidadeDeEstados()) {
return false;
}
if (a.simbolosUsados() != b.simbolosUsados()) {
return false;
}
if (a.quantidadeDeEstados() == 0) {
return true;
}
if (a.inicial() == kSemEstado || b.inicial() == kSemEstado) {
return a.inicial() == b.inicial();
}
// Percurso em largura simultâneo nos dois autômatos, visitando os símbolos
// em ordem. Se em algum ponto um tem transição e o outro não, ou as
// finalidades divergem, não há isomorfismo.
const std::vector<Simbolo> alfabeto = a.simbolosUsados();
std::map<Estado, Estado> par;
std::queue<std::pair<Estado, Estado>> fila;
par[a.inicial()] = b.inicial();
fila.push({a.inicial(), b.inicial()});
while (!fila.empty()) {
const std::pair<Estado, Estado> atual = fila.front();
fila.pop();
if (a.ehFinal(atual.first) != b.ehFinal(atual.second)) {
return false;
}
for (const Simbolo s : alfabeto) {
const Estado da = a.transicao(atual.first, s);
const Estado db = b.transicao(atual.second, s);
if ((da == kSemEstado) != (db == kSemEstado)) {
return false;
}
if (da == kSemEstado) {
continue;
}
const auto it = par.find(da);
if (it == par.end()) {
par[da] = db;
fila.push({da, db});
} else if (it->second != db) {
return false;
}
}
}
return par.size() == a.quantidadeDeEstados();
}
} // namespace peneira
A função que traça o refinamento existe por razão didática e se paga rápido: ela imprime a partição a cada rodada, e ver os blocos se dividindo é a maneira mais direta de entender que a rodada k implementa a relação \equiv_k da Definição 4.2. Aplicada ao autômato determinizado da categoria de número, que tem quarenta e três estados, ela produz três rodadas e cinco blocos, e a rodada mais instrutiva é a que separa os estados finais em dois grupos: um aceita um ponto adiante e o outro não, isto é, o algoritmo redescobriu sozinho a distinção entre parte inteira e parte fracionária, sem saber nada sobre números.
Duas decisões de implementação merecem registro. A primeira é a ordem: os estados inalcançáveis são removidos antes do refinamento, pelas razões da seção 3.3. A construção de subconjuntos não os produz, mas a função é escrita para servir também a autômatos desenhados à mão, que podem ter órfãos. A segunda é o tratamento do estado morto: o refinamento trabalha sobre a forma completa, porque a assinatura precisa de destino definido para cada símbolo, e o bloco morto é descartado na reconstrução, devolvendo a representação esparsa. Isso merece a ressalva honesta que a seção 3.2 antecipou — o autômato mínimo da teoria, com função de transição total, é este mais o estado morto de volta. Mesma linguagem, uma escolha de representação de diferença, e a unicidade vale nas duas convenções desde que não se misturem.
Aviso
Onde é fácil errar aqui. Montar a assinatura com os símbolos que o estado aceita, em vez dos blocos a que ele leva. Dois estados finais que aceitam os mesmos símbolos podem ser distinguíveis se um deles leva a um estado morto e o outro não. A assinatura precisa incluir o bloco de destino.
1.10.3 8.3 Mil duzentos e noventa e seis estados viram vinte
Com as duas etapas encadeadas, a cadeia completa fica pronta: expressão regular entra, autômato determinístico mínimo sai. A tabela abaixo mede as seis categorias léxicas da linguagem do caso conduzido nas três etapas.
| Categoria | Thompson | Determinizado | Mínimo | Redução |
|---|---|---|---|---|
| Identificador | 250 | 64 | 2 | 99,2% |
| Número | 168 | 43 | 5 | 97,0% |
| Texto | 392 | 100 | 3 | 99,2% |
| Padrão | 392 | 100 | 3 | 99,2% |
| Pontuação | 64 | 16 | 5 | 92,2% |
| Espaço | 30 | 9 | 2 | 93,3% |
| Total | 1296 | 332 | 20 |
O identificador é o caso mais instrutivo. A expressão que o descreve tem duas classes de caracteres, e a construção de Thompson expande cada uma em uma cadeia de uniões — vinte e seis fragmentos para a primeira, trinta e sete para a segunda, cada um com dois estados, mais dois estados por operador de união. Daí os duzentos e cinquenta. Só que esses vinte e seis caminhos paralelos são indistinguíveis para o autômato: depois de ler qualquer uma das letras, o conjunto de estados alcançados é o mesmo conjunto, porque o fecho vazio das saídas dos fragmentos converge para a entrada do fragmento seguinte. A construção de subconjuntos percebe isso ao consultar o dicionário, e a minimização depois observa que quase todos os estados sobreviventes aceitam exatamente o mesmo daí para a frente, fundindo tudo em dois — que são os dois estados que qualquer pessoa desenharia à mão.
É a ilustração concreta da seção 2.3: a expansão de Thompson é redundante por construção, e as duas etapas seguintes existem para desfazer redundância que ninguém quis criar. A construção não é ingênua; ela é uniforme, e a uniformidade cobra em tamanho o que entrega em simplicidade.
A demonstração do outro lado da moeda também está implementada. A família de linguagens do Teorema 2.2 é construída para valores crescentes de profundidade, e as contagens são medidas nas três etapas: a coluna do determinizado dobra a cada símbolo a mais de profundidade exigida, e a coluna do mínimo acompanha, porque a minimização não tem o que fazer — o autômato já é mínimo, e a memória exigida é da linguagem, não do método. Contrastar essa medição com a tabela das categorias reais é o ponto pedagógico: lá a determinização encolhe, aqui ela explode, e as duas coisas são verdadeiras ao mesmo tempo.
1.10.4 8.4 A unicidade posta à prova
Agora a verificação que vale o capítulo inteiro. Existem dois caminhos completamente independentes até o autômato da categoria de número: o desenho feito à mão no capítulo sobre autômatos determinísticos, e a expressão regular passada por Thompson, determinização e minimização. Nenhum dos dois sabe da existência do outro. O Teorema 6.1 diz que os dois mínimos têm de ser o mesmo autômato, a menos de renomeação dos estados.
E são. O desenho à mão tem cinco estados e a minimização confirma que ele já era mínimo — não havia gordura a cortar. O caminho automático parte de cento e sessenta e oito estados, determiniza para quarenta e três e minimiza para cinco. Os dois resultados saem isomorfos.
O teste de isomorfismo não é comparação de contagem, pela razão exposta na seção 6.2. Ele numera os dois autômatos canonicamente, por percurso em largura a partir do inicial visitando os símbolos em ordem, e exige que finalidade e estrutura de transições casem em cada passo. Dois autômatos com cinco estados cada podem ter contagens iguais e formas diferentes, e este teste recusaria.
Além da estrutura, confiro o comportamento sobre o conjunto de cadeias de teste montado no capítulo sobre expressões regulares, e os dois mínimos concordam em todos os casos. São verificações de naturezas diferentes — uma olha a forma, outra olha o que a máquina faz —, e passar nas duas é bem mais convincente que passar em qualquer uma.
Importante
O que isso destrava. No capítulo sobre expressões regulares, comparei duas expressões gerando as linguagens que elas denotam até um comprimento dado, e registrei que aquilo era evidência e não demonstração. Agora existe o procedimento de verdade: converta as duas em autômatos, minimize, teste isomorfismo. A resposta é exata e vale para cadeias de qualquer comprimento. Foi para poder dizer isto que a lacuna ficou explicitamente registrada lá atrás.
1.10.5 8.5 A exportação, e um defeito que só o diagrama revelou
A última peça é a exportação para DOT, com as convenções e o agrupamento de faixas discutidos na seção 7.
05_dot.cpp
#include "05_dot.h"
#include <fstream>
#include <map>
#include <sstream>
#include <vector>
namespace peneira {
namespace {
// Escapa o que o DOT trata como especial dentro de um rótulo entre aspas.
std::string escaparDot(Simbolo s) {
switch (s) {
case '"':
return "\\\"";
case '\\':
return "\\\\";
case ' ':
return "esp";
case '\t':
return "tab";
case '\n':
return "nl";
case '\r':
return "cr";
default:
break;
}
if (s >= 33 && s <= 126) {
return std::string(1, static_cast<char>(s));
}
std::ostringstream saida;
saida << '#' << static_cast<unsigned int>(s);
return saida.str();
}
} // namespace
std::string exportarDot(const Afd& a) {
std::ostringstream saida;
saida << "digraph automato {\n";
saida << " rankdir=LR;\n";
saida << " labelloc=\"t\";\n";
saida << " label=\"" << a.nome() << " (" << a.quantidadeDeEstados()
<< " estados)\";\n";
// Nó invisível apontando para o inicial: é a convenção usual para marcar
// o estado de partida num diagrama de autômato.
saida << " inicio [shape=point];\n";
if (a.inicial() != kSemEstado) {
saida << " inicio -> q" << a.inicial() << ";\n";
}
for (std::size_t e = 0; e < a.quantidadeDeEstados(); ++e) {
saida << " q" << e << " [shape="
<< (a.ehFinal(e) ? "doublecircle" : "circle") << "];\n";
}
// Agrupa por destino e, dentro do destino, colapsa símbolos consecutivos
// em faixa, para que o rótulo da aresta caiba no desenho.
const std::vector<Simbolo> alfabeto = a.simbolosUsados();
for (std::size_t e = 0; e < a.quantidadeDeEstados(); ++e) {
std::map<Estado, std::vector<Simbolo>> porDestino;
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(e, s);
if (destino != kSemEstado) {
porDestino[destino].push_back(s);
}
}
for (const auto& par : porDestino) {
std::ostringstream rotulo;
const std::vector<Simbolo>& simbolos = par.second;
std::size_t i = 0;
bool primeiro = true;
while (i < simbolos.size()) {
std::size_t j = i;
while (j + 1 < simbolos.size() &&
simbolos[j + 1] == static_cast<Simbolo>(simbolos[j] + 1)) {
++j;
}
if (!primeiro) rotulo << ",";
if (i == j) {
rotulo << escaparDot(simbolos[i]);
} else {
rotulo << escaparDot(simbolos[i]) << "-"
<< escaparDot(simbolos[j]);
}
primeiro = false;
i = j + 1;
}
saida << " q" << e << " -> q" << par.first << " [label=\""
<< rotulo.str() << "\"];\n";
}
}
saida << "}\n";
return saida.str();
}
bool salvarDot(const Afd& a, const std::string& caminho, std::string& erro) {
std::ofstream arquivo(caminho, std::ios::binary);
if (!arquivo) {
erro = "nao foi possivel abrir para escrita: " + caminho;
return false;
}
arquivo << exportarDot(a);
if (!arquivo) {
erro = "falha ao escrever: " + caminho;
return false;
}
erro.clear();
return true;
}
} // namespace peneira
O arquivo gerado para o autômato mínimo da categoria de número declara o grafo com orientação da esquerda para a direita, um rótulo com o nome da categoria e a contagem de estados, um nó invisível apontando para o inicial, círculo duplo para os finais e uma aresta por faixa de símbolos, com os extremos separados por hífen. É texto simples, legível mesmo sem a ferramenta de desenho instalada.
Encerro com o episódio que justifica tudo o que escrevi na seção 7.1. Ao olhar o diagrama gerado para a categoria de espaço em branco, o rótulo de uma aresta saiu listando as letras n, r e t ao lado do espaço. O autômato estava reconhecendo essas três letras como se fossem espaço em branco. A causa estava no analisador da notação, escrito no capítulo anterior: diante de uma barra invertida seguida de t, ele removia o significado especial da barra e devolvia a letra, em vez de traduzir para o caractere de tabulação.
O defeito é do pior tipo. O autômato ficava bem formado, a determinização e a minimização funcionavam perfeitamente sobre ele, os testes de estrutura passavam — e a linguagem reconhecida estava errada. Nenhuma verificação anterior o teria pego, porque o conjunto de cadeias de teste da categoria de espaço não distingue uma tabulação de uma letra t sem que alguém repare na diferença. O diagrama reparou. A correção foi acrescentar a tradução das sequências de controle nos três pontos em que a barra invertida é consumida, e o rótulo passou a listar tabulação, quebra de linha, retorno de carro e espaço.
Se você precisar de um argumento único a favor de tratar a visualização como ferramenta de trabalho e não como entrega decorativa, é este.
1.11 Síntese
A pergunta pendente está respondida: o não determinismo não aumenta o poder de reconhecimento dos autômatos finitos, e a demonstração é construtiva — é o algoritmo de subconjuntos. Os dois pontos em que se erra ao implementá-lo são a ordem entre movimento e fecho vazio, que é mover primeiro, e o estado inicial, que é o fecho do inicial. O preço é exponencial no pior caso, e o pior caso é real: a família cujo k-ésimo símbolo contado do fim é fixado exige 2^k estados em qualquer determinístico. Só que ele quase não aparece em especificações léxicas, porque os caminhos paralelos de Thompson convergem e a construção sob demanda percebe isso ao reencontrar um conjunto já visitado.
A minimização é operação de outra natureza: funde estados que nenhuma continuação distingue. O ponto difícil é que a indistinguibilidade é comportamental, e não a aparência local das transições — circularidade que obriga ao ponto fixo, e que o algoritmo de Moore resolve estratificando por comprimento de cadeia distinguidora. O resultado que dá valor a tudo é a unicidade: o mínimo é único a menos de isomorfismo, o que faz dele uma forma canônica, o que torna decidível a equivalência de linguagens regulares — pergunta que até aqui só sabíamos responder por amostragem, e portanto não sabíamos responder. E fecha o percurso a exportação para visualização, daqui em diante o principal instrumento de depuração do seu projeto.
O próximo módulo faz a pergunta oposta — não o que essa maquinaria consegue, mas o que ela não consegue —, e a resposta virá de algo que já apareceu de passagem aqui: um autômato com n estados, lendo uma cadeia mais longa que n, repete algum estado, e essa repetição é uma alavanca que se pode acionar.