stateDiagram-v2
direction LR
[*] --> repouso
repouso --> repouso: a, b
repouso --> viA: a
viA --> viAB: b
viAB --> aceita: b
aceita --> aceita: a, b
aceita --> [*]
1 Módulo 04: Não Determinismo e a Construção de Thompson
Bem-vindo ao quarto módulo. Até agora todo autômato que apareceu por aqui foi desenhado por uma pessoa. Isso acaba neste módulo: ao fim da leitura você terá a máquina que transforma uma expressão regular escrita como texto em autômato executável, sem intervenção humana. É a peça que separa um exercício de sala de um analisador léxico de verdade.
1.1 O problema: um trecho no meio do texto
Vamos por partes, começando com um problema que costuma dividir a turma ao meio.
Imagine o alfabeto de dois símbolos, a e b, e a linguagem das cadeias que contêm o trecho abb em algum lugar. A expressão regular é banal: qualquer coisa, abb, qualquer coisa. Agora desenhe o autômato determinístico. Você parte de um estado de repouso, lê um a e vai para “vi o começo”, lê um b e vai para “vi dois terços”, lê outro b e aceita para sempre.
Agora responda: estando em “vi o começo”, o que acontece se o próximo símbolo for outro a? A resposta não é voltar ao repouso — esse segundo a pode muito bem ser o início da ocorrência de verdade. E se, em “vi dois terços”, vier um a? Volta-se para “vi o começo”. Cada decisão dessas exige raciocinar sobre o que da tentativa fracassada ainda serve para a seguinte, e fica mais delicada à medida que o trecho procurado cresce.
Agora eu lhe dou uma máquina irresponsável. Ela fica no repouso lendo qualquer símbolo e, quando lê um a, também avança para “vi o começo” — as duas coisas ao mesmo tempo, sem escolher. Depois exige b, depois b, e aceita.
Quatro estados, zero decisões de retorno, quinze segundos para escrever. E a pergunta que organiza o módulo inteiro é: isso é trapaça? A intuição de quase todo estudante — a minha inclusive, quando aprendi isto — é que uma máquina que faz todas as escolhas ao mesmo tempo deve reconhecer mais linguagens do que uma que se compromete a cada passo. Essa intuição está errada, e é um dos resultados mais bonitos da teoria da computação. Os dois modelos reconhecem exatamente a mesma classe de linguagens: a máquina irresponsável não é mais poderosa, é apenas mais conveniente.
Guarde a palavra conveniente. Se dois formalismos têm o mesmo poder e conveniências diferentes, a decisão de engenharia é óbvia: especifica-se com o conveniente e executa-se com o eficiente, desde que exista tradução automática entre eles.
Antes de seguir, quero registrar em que ponto o caso conduzido deste livro chega a este capítulo, porque é a partir daí que tudo o que vem abaixo se apoia.
Duas peças já estão prontas e serão usadas sem cerimônia. A primeira é a representação da expressão regular como árvore, com os três casos base e os três construtores da definição indutiva, mais as formas derivadas montadas sobre eles. É o objeto sobre o qual a construção de Thompson opera, e ele existe desde o capítulo sobre linguagens e expressões regulares. A segunda é o autômato finito determinístico, com estados representados por índices em um vetor e transições guardadas em mapas esparsos, construído no capítulo anterior junto com os autômatos desenhados à mão para as categorias léxicas da linguagem que estamos compilando.
Esses autômatos desenhados à mão têm, neste capítulo, uma função nova e mais interessante do que a original: eles viram gabarito. A tradução automática que vamos construir precisa produzir, a partir da notação textual da mesma categoria, um autômato que dê o mesmo veredicto que o desenho manual em cada cadeia do conjunto de teste daquela categoria. Sem esse confronto, a tradução seria verificada apenas contra a intuição de quem a escreveu, o que não é verificação.
Se você chegou aqui sem ter acompanhado os dois capítulos anteriores, o que precisa trazer é: a definição de expressão regular como objeto indutivo com seis construtores, a definição de autômato finito determinístico como quíntupla, e a prática de representar estados por índices inteiros em vez de ponteiros — um autômato é um grafo com ciclos, e grafo cíclico manipulado por ponteiro é a origem mais comum de defeito de memória em um projeto como este.
1.2 O não determinismo como recurso de especificação
O autômato do módulo anterior é determinístico num sentido preciso: para cada par formado por estado e símbolo existe exatamente um destino. É essa unicidade que permite executá-lo com uma variável de estado e um laço, e é ela que impõe o trabalho de projeto que acabei de descrever.
O relaxamento troca “exatamente um estado” por “um conjunto de estados, possivelmente vazio, possivelmente com vários elementos” — e absorve dois relaxamentos de uma vez. Conjunto com vários elementos é o não determinismo propriamente dito; conjunto vazio é a ausência de transição, que no modelo determinístico precisava de um estado de erro absorvente escrito à mão e agora desaparece da especificação.
Formalmente, um autômato finito não determinístico é a quíntupla N = (Q, \Sigma, \delta, q_0, F), com a mesma leitura de sempre para os quatro primeiros componentes e a função de transição
\delta : Q \times \Sigma \to \mathcal{P}(Q).
Mudou o contradomínio, e só: onde havia Q, agora há o conjunto das partes de Q. A economia é enganosa, porque essa alteração muda o significado de executar o autômato, muda a estrutura de dados que o representa e muda o custo do reconhecimento.
1.2.1 Duas leituras, e você precisa das duas
Há duas maneiras de dar sentido à frase “a máquina não escolhe”, e a literatura troca entre elas sem avisar.
A primeira é a da adivinhação com oráculo benevolente: a cada passo a máquina escolhe uma continuação, e quem escolhe é um oráculo que sempre acerta. A cadeia é aceita quando existe um caminho que a aceita. É ótima para especificar e demonstrar, porque provar aceitação vira exibir um caminho.
A segunda é a da exploração simultânea: a máquina mantém o conjunto de todos os estados em que poderia estar e atualiza esse conjunto inteiro a cada símbolo lido, aceitando quando o conjunto final tem pelo menos um estado final. Essa leitura é perfeitamente determinística e é a única que se implementa.
A ponte entre as duas é a função de transição estendida, definida por indução sobre a cadeia: \hat{\delta}(S, \varepsilon) = S e \hat{\delta}(S, wa) = \bigcup_{q \in \hat{\delta}(S, w)} \delta(q, a). Lê-se assim: para saber onde se pode estar depois de ler wa, descubra onde se pode estar depois de w e siga, de cada um desses estados, todas as transições rotuladas por a. A união é o coração da coisa. E a linguagem reconhecida é
L(N) = \{\, w \in \Sigma^* \;\mid\; \hat{\delta}(\{q_0\}, w) \cap F \neq \emptyset \,\}.
Note que a condição de aceitação é interseção não vazia, e não pertinência: não se exige que todos os caminhos terminem em estado final, basta que algum termine.
Pare e pense. Se em vez de “algum caminho aceita” a regra fosse “todos os caminhos aceitam”, você teria um objeto diferente. A máquina irresponsável do começo ainda reconheceria a linguagem certa sob essa outra regra? A resposta diz muito sobre onde o poder do modelo realmente mora.
Um lema demonstrável por indução costura as duas leituras: p pertence a \hat{\delta}(S, w) se e somente se existe uma sequência de estados que começa em S, termina em p e respeita as transições símbolo a símbolo. É a licença para alternar entre as leituras — para convencer alguém, exibo um caminho; para calcular, acompanho conjuntos.
1.2.2 O que se ganha e o que se paga
O primeiro ganho é a união livre. No modelo determinístico, unir duas linguagens exige o produto: estados são pares, e o total é o produto dos tamanhos. No não determinístico, basta um estado inicial novo apontando para os dois iniciais originais, e o total é a soma mais um. A diferença entre soma e produto separa o que escala do que não escala — e é exatamente a operação de que um analisador léxico precisa, porque ele é a união de todos os padrões das categorias que reconhece.
O segundo ganho é a dispensa daquele raciocínio de retorno da abertura. O terceiro, o que mais importa aqui, é que a tradução a partir de expressões regulares fica composicional: cada operador vira uma forma de colar autômatos, e colar autômatos exige criar pontos de escolha, justamente o que o modelo determinístico proíbe.
| Dimensão | Determinístico | Não determinístico |
|---|---|---|
| Destino de uma transição | um estado | conjunto de estados |
| Ausência de transição | exige estado de erro explícito | é o conjunto vazio, sem custo |
| Estado da execução | uma variável | um conjunto de tamanho variável |
| Custo por símbolo lido | constante | proporcional ao conjunto ativo |
| Facilidade de especificar | baixa quando há sobreposição | alta |
| Facilidade de executar | máxima | baixa |
Três confusões que aparecem sempre. Não determinismo não é probabilidade: não há sorteio, e a aceitação é existencial. Não é paralelismo físico: há um único laço atualizando um conjunto, e duas “cópias” no mesmo estado se fundem sozinhas — é essa fusão, que a metáfora das cópias esconde, que torna a simulação viável. E não aumenta o poder de reconhecimento; aumenta a economia de descrição.
1.3 Transições vazias e o fecho vazio
O modelo ainda atrapalha num ponto: toda transição consome um símbolo. Colar dois autômatos exige, então, olhar para dentro deles, replicando nos finais do primeiro as transições que saem do inicial do segundo — o que quebra o encapsulamento.
O remédio é permitir transições que mudam o estado sem consumir símbolo — as transições vazias, ou transições épsilon. O domínio de \delta passa a ser Q \times (\Sigma \cup \{\varepsilon\}), com \varepsilon \notin \Sigma. Aquele “não pertence” parece pedantismo e não é: se você representar as vazias com um valor especial dentro do mesmo mapa das comuns, esse valor precisará ser excluído em todo lugar que percorra o alfabeto, e esquecer a exclusão em um ponto produz comportamento errado difícil de rastrear. Estrutura separada torna o esquecimento impossível. Com elas, colar dois autômatos é ligar cada final do primeiro ao inicial do segundo por uma transição vazia.
1.3.1 O conjunto dos estados que se alcança de graça
Estando num estado, a máquina pode estar, sem ler nada, em vários outros; e a partir desses, em outros ainda. Esse conjunto tem nome: fecho vazio de S, escrito E(S), o menor subconjunto de Q que contém S e é fechado sob transições vazias.
Essa formulação é elegante e não diz como calcular. A por iteração diz: comece com S e a cada passo acrescente todos os destinos vazios do que já se tem. Como cada conjunto contém o anterior e todos cabem em Q, que é finito, a cadeia estabiliza — e o ponto de estabilização é o fecho.
O fecho é extensivo, monótono, idempotente e aditivo. Extensividade garante que aplicá-lo nunca perde estados — a versão errada mais comum devolve só os estados alcançados e esquece os de partida. Idempotência autoriza aplicá-lo uma vez em cada ponto do algoritmo. Aditividade permite calculá-lo em partes, e é dela que a determinização tira proveito.
flowchart TD
A[Conjunto de partida S] --> B[resultado := S<br/>pilha := S]
B --> C{pilha vazia?}
C -- sim --> D[devolve resultado<br/>= fecho vazio de S]
C -- nao --> E[retira um estado q da pilha]
E --> F[para cada destino p<br/>de uma transicao vazia de q]
F --> G{p ja esta<br/>em resultado?}
G -- sim --> C
G -- nao --> H[insere p em resultado<br/>e empilha p]
H --> C
Olha o detalhe que apanha quase todo mundo na primeira implementação. A formulação natural é recursiva: para fechar um estado, inclua-o e feche cada destino vazio. Isso é correto em grafos acíclicos e não termina quando há ciclos de transições vazias — que não são patologia rara: a construção seguinte produz um por ocorrência do operador de repetição.
A terminação depende da marcação, não do formato do laço. Trocar recursão por pilha explícita não resolve nada — uma pilha sem marcação empilha os mesmos estados indefinidamente. O que garante a terminação é cada estado entrar na pilha no máximo uma vez. Se estiver depurando um fecho que não para, olhe a condição de inserção, não a estrutura do laço.
1.3.2 Onde o fecho entra no reconhecimento
Com o fecho definido, a transição estendida vira \hat{\delta}(S, \varepsilon) = E(S) e \hat{\delta}(S, wa) = E\!\left( \bigcup_{q \in \hat{\delta}(S, w)} \delta(q, a) \right). São dois pontos de aplicação, e os dois são obrigatórios.
O primeiro está no caso base: antes de ler qualquer coisa, a máquina já pode ter se deslocado de graça a partir do inicial. Omitir o fecho aí é o defeito que faz um autômato de expressão com repetição rejeitar a cadeia vazia — e que passa despercebido em qualquer bateria que só use cadeias não vazias. O segundo ponto está depois de cada símbolo consumido, e omiti-lo produz um autômato que reconhece um subconjunto próprio da linguagem pretendida.
E não, não é preciso aplicar o fecho antes de cada símbolo: pela idempotência, todo conjunto que aparece como argumento já é fechado. Duas aplicações por passo é desperdício; nenhuma é erro.
As transições vazias não acrescentam poder: dá para eliminá-las absorvendo o fecho dentro de cada transição comum e tornando final todo estado que alcança um final de graça. Ninguém faz isso como passo separado, porque a determinização já trata as vazias diretamente.
1.4 A equivalência entre os modelos
Chego ao resultado que responde à pergunta da abertura, devido a Michael Rabin e Dana Scott, no trabalho de 1959 sobre autômatos finitos e seus problemas de decisão, um dos motivos pelos quais receberam o Prêmio Turing em 1976: as linguagens reconhecidas por autômatos finitos determinísticos, por não determinísticos e por não determinísticos com transições vazias formam a mesma classe.
flowchart LR
D[Deterministico<br/>um destino por par] -->|inclusao imediata:<br/>ler destino como conjunto unitario| N[Nao deterministico<br/>conjunto de destinos]
N -->|absorve o fecho na transicao<br/>Teorema de eliminacao| V[Com transicoes vazias]
V -->|construcao de subconjuntos<br/>proximo modulo| D
O enunciado é sobre classes de linguagens, e insisto porque é o ponto que mais se perde na conversa informal: ele não fala de tamanho, de custo de execução nem de facilidade de escrita, apenas diz que o conjunto das linguagens alcançáveis é o mesmo.
O sentido simples é imediato: leia cada destino único como um conjunto unitário e pronto — a conversão é a identidade disfarçada de mudança de tipo, e por isso costuma ficar sem código nos projetos.
O sentido difícil merece explicação, porque entender por que ele é difícil vale mais que o enunciado. O determinístico guarda um item, o estado atual; o não determinístico, executando, guarda uma coleção de tamanho variável. Parece diferença de capacidade de armazenamento, e se fosse, os modelos não seriam equivalentes. A leitura está errada por uma razão de contagem: o conjunto ativo é sempre um subconjunto de Q, que é finito, então há 2^{|Q|} conjuntos possíveis — grande, mas finito. Um autômato determinístico com 2^{|Q|} estados tem exatamente a memória necessária para lembrar de qual subconjunto se trata. Daí o nome do algoritmo do próximo módulo: construção de subconjuntos.
E o limite exponencial não é folga da demonstração. Considere as cadeias cujo n-ésimo símbolo contado a partir do fim é um símbolo fixado: um autômato não determinístico com n+1 estados as reconhece adivinhando onde o sufixo começa, e o determinístico mínimo tem 2^n estados, porque precisa lembrar os últimos n símbolos lidos. A boa notícia é que essa família existe para forçar o pior caso, e categorias léxicas reais não se parecem com ela.
Simular já é determinizar, só que adiado
A simulação mantém um conjunto de estados e, a cada símbolo, produz outro conjunto determinado pelo anterior e pelo símbolo lido — que é exatamente a definição de uma função de transição determinística sobre o conjunto de subconjuntos. A simulação é um autômato determinístico rodando, só que com os estados calculados na hora em vez de tabelados de antemão. A diferença é apenas quando o cálculo acontece: pagar antes e uma vez, ou pagar depois e sempre. É a mesma decisão que separa compilar de interpretar.
Duas delimitações, porque teorema limpo convida a uso indevido. Os modelos são intercambiáveis quanto à linguagem reconhecida, e só: se o problema exige saber qual padrão casou, onde casou ou qual foi o casamento mais longo — as três perguntas de um analisador léxico —, a passagem de um ao outro exige carregar informação que o teorema não menciona. E a equivalência não se generaliza: nos autômatos de pilha a resposta será oposta, porque a memória é ilimitada e o argumento de contagem evapora.
1.5 A construção de Thompson
Ken Thompson publicou em 1968 o algoritmo que traduz expressão regular em autômato não determinístico, no contexto de um mecanismo de busca em texto. São seis casos, um por construtor da definição indutiva, e a simplicidade não é acidente.
Se eu tivesse de reduzir tudo a uma ideia, seria esta: cada peça produzida tem a mesma forma externa, independentemente do que tenha dentro. Um fragmento normalizado tem exatamente um estado de entrada e um de saída, distintos; nada chega à entrada; nada parte da saída. As duas últimas condições fazem o trabalho — garantem que o fragmento é uma caixa com um fio de entrada e um de saída, conectável a qualquer coisa sem que se saiba o que ela contém.
Dois estados novos e quatro transições vazias: da nova entrada para as entradas dos dois fragmentos, e das saídas dos dois para a nova saída. Da nova entrada, a máquina mergulha de graça em qualquer um dos dois; uma vez dentro, fica presa àquele. Os dois estados novos são necessários: usar a entrada de um dos operandos como entrada comum faria essa entrada receber transição, e se aquele operando tiver uma repetição no topo, o laço de volta criaria caminhos que misturam as alternativas. Não é sutileza teórica; é defeito.
Nenhum estado novo. Uma única transição vazia da saída do primeiro para a entrada do segundo, com entrada e saída do resultado herdadas das pontas. O salto é obrigatório porque, pela invariante, nada mais sai da saída do primeiro e nada mais chega à entrada do segundo. Existe a tentação de fundir os dois estados; a construção resultante é correta, mas o estado fundido deixa de satisfazer a invariante, e os casos especiais voltam nos outros cinco casos.
Dois estados novos e quatro transições vazias: da nova entrada para a entrada interna, da nova entrada direto para a nova saída, da saída interna para a nova saída, e — esta é a que importa — da saída interna de volta para a entrada interna. A transição direta dá conta da repetição de zero ocorrências, e é por ela que a estrela aceita a cadeia vazia mesmo quando o operando não aceita; o laço de volta permite atravessar o interior quantas vezes se queira.
flowchart LR
i((i)) -->|vazia| ir((entrada de Nr))
i -->|vazia: zero ocorrencias| f((f))
subgraph Nr[fragmento interno de r]
ir -.-> fr((saida de Nr))
end
fr -->|vazia| f
fr -->|vazia: laco de volta| ir
Os três casos base usam dois estados cada: a linguagem vazia é o par sem transição alguma; a cadeia vazia é o par ligado por uma transição vazia; e um símbolo é o par ligado por uma transição rotulada com ele.
Este é o caso que cria ciclos de transições vazias. O laço de volta liga a saída interna à entrada interna; se o fragmento interno já tiver um caminho de transições vazias de uma à outra — o que acontece quando o operando é ele mesmo uma repetição —, fecha-se um ciclo percorrível sem consumir símbolo. É a situação que obriga o cálculo do fecho a marcar visitados.
A correção sai por indução estrutural, com hipótese dupla: para cada subexpressão, o fragmento é normalizado e denota a linguagem certa. Carregar as duas coisas juntas faz a demonstração caber em meia página, porque “a entrada não recebe transições” é o que garante que os caminhos se decompõem de maneira única.
Quanto ao custo, a conta é exata. Casos base, união e estrela gastam dois estados cada, a concatenação não gasta nenhum; com n folhas e u ocorrências de união e estrela, o total é
|Q| = 2n + 2u,
no máximo dois estados e quatro transições por nó da árvore, e nenhum estado com mais de duas saídas. Linear, portanto. A má notícia vem da notação: classes de caracteres não são construtores da teoria. Uma classe é abreviação para uma união de símbolos, e a construção expande e paga por cada um: uma classe com k símbolos custa 4k - 2 estados, trinta e oito para uma faixa de dez dígitos e cento e dois para as vinte e seis letras. A classe negada depende do alfabeto inteiro — negar um símbolo num alfabeto de cem produz quase quatrocentos estados para um único átomo. A construção troca tamanho por uniformidade.
As formas derivadas são todas abreviações, e implementá-las assim é o que mantém o algoritmo com seis casos. Uma-ou-mais reduz-se a uma ocorrência seguida da estrela; zero-ou-uma, à união com a cadeia vazia — e é aí que aquele caso base aparentemente inútil ganha função. Classe, faixa, ponto e negação reduzem-se a uniões de símbolos, e as três últimas exigem um alfabeto declarado e finito, porque complementar só faz sentido dentro de um universo.
1.6 Da notação ao texto: o analisador que ninguém anuncia
Enunciei Thompson como uma tradução de expressão regular em autômato, e essa formulação esconde uma etapa que ocupa metade do trabalho real. A construção opera sobre a árvore da expressão, mas expressões regulares não chegam como árvores — chegam como texto, e quem atravessa esse abismo é um analisador. Enquanto os autômatos eram poucos, dava para montar as árvores chamando construtores em código; isso é insuportável para meia dúzia de padrões e impossível quando eles vêm do programa do usuário. Há uma circularidade agradável aqui, e é deliberada: estamos escrevendo um analisador sintático vários módulos antes de estudar análise sintática, porque a notação é pequena o bastante para caber na intuição.
flowchart TD
A[Alternativa<br/>constroi uniao<br/>separador: barra vertical] --> B[Concatenacao<br/>constroi concatenacao<br/>sem operador escrito]
B --> C[Repeticao<br/>aplica sufixos<br/>estrela, mais, opcional]
C --> D[Atomo<br/>caractere, escape,<br/>classe, ponto, grupo]
D -->|grupo entre parenteses| A
O primeiro problema é a precedência. Dois símbolos justapostos seguidos de barra vertical e um terceiro admitem duas leituras que denotam linguagens diferentes, e a convenção universal tem três níveis: a união liga mais fraco, a concatenação liga mais forte que ela, e os sufixos de repetição ligam mais forte que a concatenação. A técnica que codifica isso num analisador de descida recursiva é escrever uma função por nível, do mais fraco ao mais forte, cada uma chamando a seguinte — e o átomo, ao encontrar um parêntese, volta ao topo. Nenhuma função precisa conhecer a tabela de precedências, porque a tabela é a ordem das chamadas.
Os três níveis não são simétricos: a concatenação é a justaposição, não tem caractere que a escreva. O laço da união pergunta “o próximo caractere é a barra vertical?”; o da concatenação precisa perguntar “o que vem a seguir pode iniciar um operando?” — o que exige uma lista explícita do que para o laço: o fim do texto; a barra vertical, que pertence ao nível de cima; e o parêntese de fechamento, que pertence ao átomo que abriu o grupo.
Pergunta para levar adiante. O que acontece se você esquecer o parêntese de fechamento nessa lista de parada? A concatenação engole o fecho do grupo como se fosse operando, o átomo que abriu o grupo nunca encontra o seu fechamento, e o erro é reportado três níveis acima, apontando para o lugar errado. Se um analisador de descida recursiva estiver reclamando de outro planeta, confira o conjunto de parada de cada laço.
O nível do átomo concentra os detalhes chatos. O escape exige verificar que existe caractere após a barra invertida. A classe é a mais trabalhosa: precisa distinguir símbolo isolado, faixa de dois símbolos separados por hífen, e hífen que é ele próprio símbolo — distinção que depende de olhar um caractere adiante e conferir que ele não é o colchete de fechamento. Escrever isso com descuido faz a classe engolir o fechamento como extremo superior da faixa. Recuse ainda a classe vazia e a faixa com extremos invertidos: as duas denotam a linguagem vazia e são quase sempre erro de digitação.
Sobre erros, três regras. Toda falha carrega posição — “expressão inválida” diante de um padrão de quarenta caracteres é inútil, enquanto “esperava-se um operando na posição vinte e três” resolve tudo em segundos. Preserve a primeira falha, porque as seguintes são quase sempre consequência dela. E, na dúvida, recuse: um analisador que aceita expressão duvidosa transfere o problema para Thompson, que gerará um autômato reconhecendo algo que ninguém pediu — o pior tipo de defeito, porque é silencioso. Daí também o teste que interessa: as expressões inválidas, de parêntese aberto sem fechar a barra invertida no fim do texto. Uma bateria só de expressões válidas dá nota máxima a um analisador que aceita tudo.
1.7 A tradução em funcionamento
flowchart LR
T[Texto da expressao] --> P[Analisador da notacao<br/>precedencia em camadas]
P --> A[Arvore da expressao]
A --> TH[Construcao de Thompson<br/>seis casos]
TH --> N[Automato nao deterministico<br/>com transicoes vazias]
N --> S[Simulacao com fecho vazio<br/>conjunto de estados ativos]
S --> V[Veredicto sobre a cadeia]
G[Automato desenhado a mao<br/>do modulo anterior] --> V2[Veredicto de referencia]
V --- V2
No caso conduzido, duas medidas interessam. A primeira é o veredicto: o autômato gerado tem de aceitar e rejeitar as mesmas cadeias que o desenhado à mão — e o conjunto de teste precisa sobretudo das cadeias a rejeitar, porque um autômato que aceita tudo passaria numa bateria só de positivas. A segunda é o tamanho, lado a lado; o contraste é o enunciado do problema que o próximo módulo resolve.
1.7.1 6.1 O analisador da mini-notação
A notação que o compilador da Peneira aceita é o recorte discutido na seção anterior, com uma decisão de escopo registrada explicitamente: entram os seis construtores da teoria e as formas derivadas — repetição opcional, uma-ou-mais, classes com faixa, classes negadas, ponto e parênteses; ficam de fora contadores do tipo {m,n}, grupos de captura, retrovisores e âncoras.
O motivo de cada exclusão vale mais do que a lista. Os retrovisores ficaram de fora porque não são regulares: uma notação que permite exigir a repetição literal de um trecho já casado descreve linguagens fora da classe que este livro estuda, e incluí-los seria sair do território sem avisar. Âncoras não fazem sentido fora de um mecanismo de busca em texto corrido. E os contadores são açúcar puro, no sentido de que se expandem em concatenações e opcionais sem acrescentar nada de novo à teoria, ao custo de inflar a árvore.
A interface do analisador declara a gramática suportada e o alfabeto adotado, e as duas declarações estão no mesmo lugar de propósito — o alfabeto é o que dá significado ao ponto e à negação, e escondê-lo dentro da implementação seria esconder metade da semântica.
04_notacao.h
#ifndef PENEIRA_04_NOTACAO_H
#define PENEIRA_04_NOTACAO_H
#include <cstddef>
#include <string>
#include <vector>
#include "02_regex.h"
#include "03_afd.h"
namespace peneira {
// O alfabeto sobre o qual a notação opera. Precisa ser declarado e finito
// porque o ponto e as classes negadas são definidos por complemento: `.` é a
// união de todos os símbolos do alfabeto, e `[^"]` é a união de todos menos um.
// Sem alfabeto fixado, nenhuma das duas construções tem significado.
//
// Adotei o ASCII imprimível mais tabulação, retorno e nova linha. É o conjunto
// que os programas Peneira usam de fato, e mantê-lo pequeno importa: cada
// símbolo do alfabeto vira dois estados na construção de Thompson quando
// aparece numa classe negada.
const std::vector<Simbolo>& alfabetoDaNotacao();
// Resultado da análise. Em caso de falha, a posição aponta o caractere em que
// o analisador desistiu — sem posição, a mensagem de erro é inútil.
struct ResultadoNotacao {
RegexPtr expressao;
bool ok = false;
std::string erro;
std::size_t posicao = 0;
};
// Analisa a mini-notação de expressões regulares e devolve a árvore do módulo 2.
//
// Gramática suportada, em descida recursiva:
//
// alt := concat ( "|" concat )*
// concat := repeticao+
// repeticao := atomo ( "*" | "+" | "?" )*
// atomo := CARACTERE | "." | "[" classe "]" | "(" alt ")" | "\" CARACTERE
// classe := "^"? ( CARACTERE "-" CARACTERE | CARACTERE )+
//
// Escolhas registradas: sem contadores `{m,n}`, sem grupos de captura, sem
// retrovisores e sem âncoras. Os três últimos não são regulares ou não fazem
// sentido fora de um motor de busca; o primeiro é açúcar que expandiria a
// árvore sem ensinar nada de novo.
ResultadoNotacao analisarNotacao(const std::string& texto);
} // namespace peneira
#endif // PENEIRA_04_NOTACAO_H
O alfabeto que fixei é o ASCII imprimível mais tabulação, retorno e nova linha, o que dá noventa e oito símbolos. É o conjunto que os programas Peneira usam de fato, e mantê-lo pequeno tem consequência direta no tamanho dos autômatos, pela conta da seção 4.8: cada símbolo do alfabeto vira dois estados quando aparece na expansão de uma classe negada.
Duas escolhas de implementação merecem registro. A primeira é que o resultado da análise carrega, além da árvore, um indicador de sucesso, uma mensagem e a posição do caractere em que o analisador desistiu — a política da subseção 5.5 materializada na estrutura de retorno, e não deixada a cargo de quem chama. A segunda é que sufixos de repetição encadeados são aceitos, pela idempotência da estrela, e a decisão está comentada no código para que ninguém a confunda com descuido.
1.7.2 6.2 O autômato não determinístico e a construção
O autômato de destino difere do determinístico do capítulo anterior em duas coisas, e as duas mudam a estrutura de dados: um par de estado e símbolo leva a um conjunto de estados, e existem transições que não consomem símbolo.
04_afn.h
#ifndef PENEIRA_04_AFN_H
#define PENEIRA_04_AFN_H
#include <cstddef>
#include <map>
#include <set>
#include <string>
#include <vector>
#include "02_cadeia.h"
#include "03_afd.h"
namespace peneira {
// Autômato finito não determinístico com transições vazias.
//
// Duas diferenças em relação ao determinístico do módulo 3, e ambas mudam a
// estrutura de dados: um par (estado, símbolo) leva a um CONJUNTO de estados,
// e existem transições que não consomem símbolo algum. Guardo as vazias
// separadas das demais em vez de reservar um símbolo especial para elas —
// reservar um símbolo obrigaria a excluí-lo do alfabeto e a lembrar disso em
// todo lugar.
//
// Os fragmentos produzidos pela construção de Thompson têm exatamente um
// estado inicial e um final, e a classe assume isso.
class Afn {
public:
explicit Afn(std::string nome);
Estado novoEstado();
void adicionarTransicao(Estado de, Simbolo simbolo, Estado para);
void adicionarVazia(Estado de, Estado para);
void definirInicial(Estado e);
void definirFinal(Estado e);
const std::string& nome() const noexcept;
Estado inicial() const noexcept;
Estado final() const noexcept;
std::size_t quantidadeDeEstados() const noexcept;
std::size_t quantidadeDeTransicoes() const;
std::size_t quantidadeDeVazias() const;
// Fecho vazio: todos os estados alcançáveis a partir do conjunto dado sem
// consumir símbolo algum, incluindo os próprios estados de partida.
// É a peça que o módulo 5 vai reutilizar dentro da determinização.
std::set<Estado> fechoVazio(const std::set<Estado>& conjunto) const;
// Conjunto de estados alcançáveis consumindo exatamente um símbolo.
std::set<Estado> mover(const std::set<Estado>& conjunto, Simbolo simbolo) const;
// Simulação: acompanha um conjunto de estados em vez de um só. Funciona, e
// é cara — a cada entrada refaz o cálculo de fechos e conjuntos que o
// módulo 5 fará uma vez só, na determinização.
bool aceita(const Cadeia& s) const;
// Símbolos que aparecem em alguma transição não vazia.
std::vector<Simbolo> simbolosUsados() const;
// Acesso usado pela determinização do módulo 5.
const std::map<Simbolo, std::set<Estado>>& transicoesDe(Estado e) const;
std::string resumo() const;
private:
std::string nome_;
Estado inicial_ = kSemEstado;
Estado final_ = kSemEstado;
std::vector<std::map<Simbolo, std::set<Estado>>> transicoes_;
std::vector<std::set<Estado>> vazias_;
};
} // namespace peneira
#endif // PENEIRA_04_AFN_H
Guardei as transições vazias em um campo separado das demais, em vez de reservar um símbolo especial para representá-las dentro do mesmo mapa. A alternativa é comum e tem um custo escondido, que é exatamente o que a Definição 2.1 antecipou: o símbolo reservado precisa ser excluído do alfabeto em todo lugar que percorre símbolos, e esquecer a exclusão em um único ponto produz comportamento errado difícil de rastrear. Dois campos distintos tornam o esquecimento impossível.
A interface expõe o fecho vazio e a operação de mover por um símbolo como funções públicas, e não como detalhes internos da simulação. Isso é deliberado: as duas são as peças que a determinização do próximo capítulo vai reutilizar tal como estão, e deixá-las escondidas dentro do reconhecimento obrigaria a duplicá-las lá.
A construção de Thompson, por sua vez, tem uma interface de uma linha, e a sua interface curta é o melhor indício de que a invariante está funcionando — ela recebe uma árvore e devolve um autômato, sem parâmetros de configuração, sem casos a selecionar.
04_thompson.h
#ifndef PENEIRA_04_THOMPSON_H
#define PENEIRA_04_THOMPSON_H
#include <string>
#include "02_regex.h"
#include "04_afn.h"
namespace peneira {
// Construção de Thompson: traduz a árvore de uma expressão regular no autômato
// finito não determinístico correspondente.
//
// A propriedade que faz a construção funcionar é a composicionalidade: cada
// fragmento produzido tem exatamente UM estado de entrada e UM de saída, e
// nenhuma transição entra na entrada ou sai da saída por fora do fragmento.
// Com essa uniformidade, compor dois fragmentos é ligar saída de um à entrada
// de outro por transição vazia — sem caso especial, sem inspecionar o que há
// dentro. É por isso que a construção tem seis casos e não vinte.
Afn thompson(const Regex& r, std::string nome);
} // namespace peneira
#endif // PENEIRA_04_THOMPSON_H
Segui a recomendação da subseção 4.5 e não fundi a saída de um fragmento com a entrada do seguinte na concatenação. A economia seria de um estado por concatenação, e o preço seria a invariante da Definição 4.1 — e, com ela, os casos especiais que a invariante dispensa. Os estados excedentes serão eliminados pela minimização, de graça, no capítulo seguinte.
1.7.3 6.3 O confronto com o gabarito
A verificação da tradução é o confronto que anunciei: o autômato gerado a partir da notação da categoria numérica e o autômato desenhado à mão no capítulo anterior para a mesma categoria têm de dar o mesmo veredicto em cada uma das treze cadeias do conjunto de teste daquela categoria — as seis que devem ser aceitas e as sete que devem ser rejeitadas.
04_demos.cpp
#include "04_demos.h"
#include <ostream>
#include <set>
#include <string>
#include <vector>
#include "02_lexico.h"
#include "03_afd.h"
#include "03_reconhecedores.h"
#include "04_afn.h"
#include "04_notacao.h"
#include "04_thompson.h"
namespace peneira::demo {
namespace {
std::string conjuntoEmTexto(const std::set<Estado>& c) {
std::string saida = "{";
bool primeiro = true;
for (const Estado e : c) {
if (!primeiro) saida += ", ";
saida += "q" + std::to_string(e);
primeiro = false;
}
return saida + "}";
}
// Constrói o autômato de uma categoria a partir da notação registrada na
// especificação léxica do módulo 2.
Afn deNotacao(const std::string& notacao, const std::string& nome) {
const ResultadoNotacao r = analisarNotacao(notacao);
if (!r.ok) {
return Afn(nome + " (falhou)");
}
return thompson(*r.expressao, nome);
}
} // namespace
void mostrarAnaliseDaNotacao(std::ostream& out) {
out << "alfabeto declarado: " << alfabetoDaNotacao().size() << " simbolos\n\n";
const std::vector<std::string> exemplos{
"a", "ab", "a|b", "a*", "a+", "a?", "(a|b)*c", "[a-z]", "[0-9]+",
"-?[0-9]+(\\.[0-9]+)?",
};
out << "expressoes aceitas pela notacao:\n";
for (const std::string& e : exemplos) {
const ResultadoNotacao r = analisarNotacao(e);
out << " " << e << " -> ";
if (r.ok) {
const std::string forma = formatarRegex(*r.expressao);
out << (forma.size() > 46 ? forma.substr(0, 43) + "..." : forma)
<< " (" << forma.size() << " caracteres expandidos)\n";
} else {
out << "ERRO: " << r.erro << " na posicao " << r.posicao << '\n';
}
}
out << "\nexpressoes que a notacao recusa, com a posicao do erro:\n";
const std::vector<std::string> ruins{"", "(a", "a)", "*a", "[a", "[]",
"[z-a]", "a\\"};
for (const std::string& e : ruins) {
const ResultadoNotacao r = analisarNotacao(e);
out << " \"" << e << "\" -> "
<< (r.ok ? std::string("aceitou (nao deveria)")
: r.erro + " na posicao " + std::to_string(r.posicao))
<< '\n';
}
}
void mostrarFechoVazio(std::ostream& out) {
// a* tem o ciclo de transicoes vazias que a estrela cria.
const ResultadoNotacao r = analisarNotacao("a*");
const Afn automato = thompson(*r.expressao, "a*");
out << automato.resumo() << "\n\n";
out << "estado inicial: q" << automato.inicial() << ", final: q"
<< automato.final() << "\n\n";
const std::set<Estado> inicio{automato.inicial()};
out << "fecho vazio de " << conjuntoEmTexto(inicio) << " = "
<< conjuntoEmTexto(automato.fechoVazio(inicio)) << '\n';
out << " sem consumir simbolo algum, o automato ja esta em varios\n"
<< " estados ao mesmo tempo — inclusive no final, que e o que faz\n"
<< " a cadeia vazia ser aceita por a*.\n\n";
const std::set<Estado> apos = automato.fechoVazio(
automato.mover(automato.fechoVazio(inicio), static_cast<Simbolo>('a')));
out << "apos consumir 'a': " << conjuntoEmTexto(apos) << '\n';
out << " o laco de volta da estrela reaparece aqui: o conjunto contem\n"
<< " de novo a entrada do fragmento, pronta para outro 'a'.\n\n";
out << "aceita cadeia vazia? " << (automato.aceita("") ? "sim" : "nao")
<< "\naceita \"aaa\"? " << (automato.aceita("aaa") ? "sim" : "nao")
<< "\naceita \"ab\"? " << (automato.aceita("ab") ? "sim" : "nao") << '\n';
}
void mostrarThompson(std::ostream& out) {
out << "cada construtor da expressao vira um fragmento de tamanho fixo:\n\n";
const std::vector<std::string> exemplos{"a", "ab", "a|b", "a*", "(a|b)*"};
for (const std::string& e : exemplos) {
const ResultadoNotacao r = analisarNotacao(e);
const Afn automato = thompson(*r.expressao, e);
out << " " << e << " -> " << automato.quantidadeDeEstados()
<< " estados, " << automato.quantidadeDeTransicoes()
<< " com simbolo, " << automato.quantidadeDeVazias() << " vazias\n";
}
out << "\nDois estados por simbolo, mais dois por uniao e dois por\n"
<< "estrela. A concatenacao nao cria estado: so liga a saida de um\n"
<< "fragmento a entrada do outro.\n\n";
out << "agora as categorias reais da especificacao lexica:\n";
for (const CategoriaLexica& c : especificacaoLexica()) {
const ResultadoNotacao r = analisarNotacao(c.notacao);
if (!r.ok) {
out << " " << c.nome << ": notacao fora da mini-linguagem — "
<< r.erro << " na posicao " << r.posicao << '\n';
continue;
}
const Afn automato = thompson(*r.expressao, c.nome);
out << " " << c.nome << ": " << automato.quantidadeDeEstados()
<< " estados\n";
}
}
void mostrarConfronto(std::ostream& out) {
out << "o automato gerado precisa reconhecer exatamente o que o automato\n"
<< "construido a mao no modulo 3 reconhece.\n\n";
const ResultadoNotacao r = analisarNotacao("-?[0-9]+(\\.[0-9]+)?");
const Afn gerado = thompson(*r.expressao, "NUMERO gerado");
const Afd manual = afdNumero();
out << " a mao (modulo 3): " << manual.quantidadeDeEstados() << " estados\n";
out << " gerado (Thompson): " << gerado.quantidadeDeEstados()
<< " estados\n\n";
std::size_t conferem = 0;
std::size_t divergem = 0;
for (const CategoriaLexica& c : especificacaoLexica()) {
if (c.nome != "NUMERO") continue;
for (const Cadeia& cadeia : c.aceitas) {
const bool a = manual.aceita(cadeia);
const bool b = gerado.aceita(cadeia);
if (a == b && a) {
++conferem;
} else {
++divergem;
out << " DIVERGE em \"" << cadeia << "\": manual="
<< (a ? "aceita" : "rejeita") << ", gerado="
<< (b ? "aceita" : "rejeita") << '\n';
}
}
for (const Cadeia& cadeia : c.rejeitadas) {
const bool a = manual.aceita(cadeia);
const bool b = gerado.aceita(cadeia);
if (a == b && !a) {
++conferem;
} else {
++divergem;
out << " DIVERGE em \"" << cadeia << "\": manual="
<< (a ? "aceita" : "rejeita") << ", gerado="
<< (b ? "aceita" : "rejeita") << '\n';
}
}
}
out << " veredictos iguais: " << conferem << ", divergentes: " << divergem
<< '\n';
out << "\nO gerado tem muito mais estados e reconhece a mesma linguagem.\n"
<< "Essa folga e o preco da uniformidade da construcao — e e ela que\n"
<< "a determinizacao e a minimizacao do modulo 5 vao cobrar de volta.\n";
}
} // namespace peneira::demo
Repare que o confronto compara veredictos e exige que a concordância seja no valor esperado, em vez de apenas contar acertos de um lado. Um confronto que só verificasse concordância entre os dois autômatos passaria se ambos estivessem errados do mesmo jeito, e um confronto que só usasse as cadeias a aceitar passaria com um autômato que aceita tudo — defeito plausível, bastaria marcar o estado errado como final. São as sete cadeias a rejeitar que têm poder de detecção.
O relatório imprime também a contagem de estados dos dois, e o contraste é o resultado mais eloquente deste capítulo:
a mao (capitulo anterior): 5 estados
gerado (Thompson): 168 estados
veredictos iguais: 13, divergentes: 0Cento e sessenta e oito estados contra cinco, para reconhecer exatamente a mesma linguagem, com veredicto idêntico nas treze cadeias. A conta da seção 4.8 explica o número inteiro: as faixas de dez dígitos da expressão, expandidas em dez símbolos cada, respondem pela maior parte do inchaço, a trinta e oito estados por ocorrência. Nada disso foi escolhido por alguém; tudo veio das seis regras aplicadas sem exceção.
A demonstração do fecho vazio usa a menor expressão que contém o ciclo, que é um símbolo sob estrela: quatro estados, uma transição com símbolo e quatro vazias. O fecho vazio do estado inicial sai como um conjunto de três estados que já inclui o final, sem consumir símbolo algum — e é exatamente isso que faz a expressão aceitar a cadeia vazia, tornando concreto o ponto de aplicação do fecho no caso base da Definição 2.3. Depois de consumir um símbolo, o conjunto passa a conter de novo a entrada do fragmento interno, que é o laço de volta da estrela aparecendo no resultado, pronto para outra ocorrência. Ver o conjunto crescer e voltar torna o ciclo concreto de um jeito que a descrição não alcança.
Somando as seis categorias da especificação léxica, a construção produz mil duzentos e noventa e seis estados para reconhecer as categorias de uma linguagem minúscula, com a categoria de texto entre aspas custando sozinha trezentos e noventa e dois — aquele caso extremo da classe negada, que a conta da seção 4.8 prevê exatamente. Vale olhar esse total como o enunciado do problema do próximo capítulo.
1.8 Síntese
O não determinismo troca o destino único por um conjunto de destinos possíveis, e admite duas leituras equivalentes: a adivinhação com oráculo, boa para especificar e demonstrar, e a exploração simultânea, que é a que se implementa. O ganho é de conveniência — união passa a custar soma em vez de produto, o raciocínio sobre retornos desaparece, e a tradução a partir de expressões regulares fica composicional —, e o preço é o custo de execução. As transições vazias são o segundo relaxamento, existem para colar autômatos sem inspecionar o interior deles e obrigam a introduzir o fecho vazio, calculado por busca em grafo com marcação de visitados; a marcação não é otimização, é o que garante terminação diante dos ciclos que a estrela cria.
A equivalência entre os três modelos afirma que a classe de linguagens é a mesma, e nada sobre tamanho ou custo. O sentido difícil apoia-se num argumento de contagem: o conjunto ativo, embora variável, é sempre um dos 2^n subconjuntos de um conjunto finito. E ela não sobe de andar — nos autômatos de pilha, o não determinismo passa a acrescentar poder de verdade. Já a construção de Thompson é a ponte automática entre a notação e a máquina, com simplicidade que decorre inteiramente da invariante de fragmento normalizado; o custo é linear no tamanho da expressão, embora as classes de caracteres, sendo abreviações para uniões, produzam autômatos desproporcionais ao que descrevem. E há a etapa que o enunciado esconde: traduzir exige antes ler.
Volto à pergunta da abertura. A máquina irresponsável não era trapaça: era conveniência legítima, cobrada em tempo de execução. O próximo módulo paga essa conta de uma vez — construção de subconjuntos, eliminação de estados inalcançáveis e minimização, com o resultado de unicidade que permite decidir se duas especificações descrevem a mesma linguagem. É também onde a contagem de estados despenca, e você vai poder medir quanto da folga de Thompson era desperdício de fato.