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 — Resumo
Esta é a versão de revisão. Recapitulo aqui, em ritmo de véspera, o que este módulo tem de guardado; nada é demonstrado por inteiro, e para isso existem a versão completa do material deste módulo e o livro. Use este texto para conferir se você consegue reconstruir de cabeça o caminho que vai de uma expressão escrita como texto até um autômato executável.
Desenhe, sem consultar nada, o autômato determinístico das cadeias que contêm o trecho abb em algum lugar. Você vai travar na mesma pergunta que trava todo mundo: estando em “já vi o a”, o que fazer se vier outro a? Voltar ao repouso é errado, porque esse segundo a pode ser o começo da ocorrência de verdade. Guarde esse incômodo — o módulo inteiro existe para dispensá-lo.
1.1 O não determinismo como recurso de especificação
Agora imagine uma máquina irresponsável: no repouso ela lê qualquer símbolo e, quando lê um a, também avança para “vi o começo”, as duas coisas ao mesmo tempo. Depois exige b, depois b, e aceita. Quatro estados, zero decisões de retorno.
Isso é trapaça? A intuição diz que sim, e a intuição erra. Um autômato finito não determinístico é a quíntupla N = (Q, \Sigma, \delta, q_0, F) com a mesma leitura de sempre e uma única alteração na transição:
\delta : Q \times \Sigma \to \mathcal{P}(Q).
Onde havia Q, agora há o conjunto das partes de Q. A mudança parece de nada e absorve dois relaxamentos: conjunto com vários elementos é o não determinismo propriamente dito, e conjunto vazio é a ausência de transição, que antes exigia um estado de erro absorvente escrito à mão.
Há duas leituras da frase “a máquina não escolhe”, e você precisa das duas. A da adivinhação com oráculo benevolente diz que a cada passo alguém escolhe a continuação certa, e a cadeia é aceita quando existe um caminho que a aceita; serve para especificar e demonstrar, porque provar aceitação vira exibir um caminho. A da exploração simultânea diz que a máquina mantém o conjunto de todos os estados em que poderia estar e atualiza o conjunto inteiro a cada símbolo; essa é perfeitamente determinística e é a única que se implementa. A ponte entre elas é a transição estendida, \hat{\delta}(S, \varepsilon) = S e \hat{\delta}(S, wa) = \bigcup_{q \in \hat{\delta}(S, w)} \delta(q, a), com a linguagem reconhecida sendo
L(N) = \{\, w \in \Sigma^* \;\mid\; \hat{\delta}(\{q_0\}, w) \cap F \neq \emptyset \,\}.
Repare que a aceitação é interseção não vazia, não pertinência: basta que algum caminho termine em final.
Pare e pense. Se a regra fosse “todos os caminhos aceitam” em vez de “algum caminho aceita”, a máquina irresponsável ainda reconheceria a linguagem certa? A resposta diz onde o poder do modelo mora de verdade.
O ganho principal é a união livre: no determinístico, unir duas linguagens exige o produto dos tamanhos; no não determinístico, um estado inicial novo apontando para os dois iniciais originais dá a soma mais um. Soma contra produto separa o que escala do que não escala, e é exatamente a operação de que um analisador léxico precisa, já que ele é a união de todos os padrões que reconhece. O segundo ganho é o fim do raciocínio de retorno da abertura; o terceiro, que a tradução a partir de expressões regulares fica composicional. O preço vem na execução: em vez de uma variável de estado, um conjunto de tamanho variável, com custo por símbolo proporcional a ele.
Três confusões para não cometer na prova. Não determinismo não é probabilidade — a aceitação é existencial, não há sorteio. Não é paralelismo físico — há um laço só atualizando um conjunto, e duas “cópias” no mesmo estado se fundem sozinhas, fusão que a metáfora das cópias esconde e que torna a simulação viável. E não aumenta o poder de reconhecimento, aumenta a economia de descrição.
1.2 Transições vazias e o fecho vazio
Ainda falta uma coisa. Toda transição consome símbolo, então colar dois autômatos exige olhar para dentro deles e replicar transições — o que quebra o encapsulamento. O remédio é a transição vazia, que muda de estado sem consumir nada: o domínio de \delta passa a Q \times (\Sigma \cup \{\varepsilon\}), com \varepsilon \notin \Sigma. Esse “não pertence” não é pedantismo: representar as vazias com um valor especial dentro do mesmo mapa obriga a excluí-lo em todo percurso do alfabeto, e esquecer a exclusão em um ponto produz defeito silencioso.
Estando num estado, a máquina pode estar, de graça, em vários outros — e a partir desses, em outros ainda. Esse conjunto é o fecho vazio de S, escrito E(S): o menor subconjunto de Q que contém S e é fechado sob transições vazias. A definição é elegante e muda quanto ao cálculo; a versão iterativa acrescenta a S os destinos vazios do que já se tem até estabilizar, o que sempre acontece porque Q é finito.
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
O fecho é extensivo, monótono, idempotente e aditivo. Extensividade garante que aplicá-lo nunca perde estados — o erro mais comum devolve só os alcançados e esquece os de partida. Idempotência autoriza aplicá-lo uma vez por ponto do algoritmo. Aditividade permite calcular em partes, e é dela que a determinização tira proveito.
A terminação depende da marcação, não do formato do laço. A formulação recursiva natural não termina quando há ciclo de transições vazias, e ciclo não é patologia rara: a construção deste módulo produz um por ocorrência de repetição. Trocar recursão por pilha explícita não resolve — uma pilha sem marcação empilha os mesmos estados para sempre. Se um fecho não parar, olhe a condição de inserção.
Com o fecho, 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), e os dois pontos de aplicação são obrigatórios. Omitir o do caso base é o defeito que faz um autômato de expressão com repetição rejeitar a cadeia vazia, e que passa despercebido em qualquer bateria de teste sem cadeia vazia; omitir o de depois de cada símbolo produz um autômato que reconhece menos do que deveria. Aplicar o fecho antes de cada símbolo é desperdício: pela idempotência, todo conjunto que chega já está fechado.
1.3 A equivalência entre os modelos
Aqui está a resposta à pergunta da abertura, devida a Michael Rabin e Dana Scott no trabalho de 1959 sobre autômatos finitos e seus problemas de decisão, um dos motivos do Prêmio Turing que receberam em 1976: as linguagens reconhecidas por autômatos determinísticos, não determinísticos e 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 não diz nada sobre tamanho, custo de execução ou facilidade de escrita. O sentido fácil é imediato: leia cada destino único como conjunto unitário. O sentido difícil merece atenção, e entender por que ele é difícil vale mais que o enunciado. O determinístico guarda um item; o não determinístico, executando, guarda uma coleção de tamanho variável — parece diferença de capacidade de memória. Não é, por uma razão de contagem: o conjunto ativo é sempre um dos 2^{|Q|} subconjuntos de um conjunto finito, e um autômato determinístico com 2^{|Q|} estados tem exatamente a memória de que precisa. Daí o nome do algoritmo do próximo módulo, construção de subconjuntos. E o expoente não é folga da demonstração: nas cadeias cujo n-ésimo símbolo contado a partir do fim é fixado, o não determinístico usa n+1 estados e o determinístico mínimo usa 2^n.
Duas delimitações. Os modelos são intercambiáveis quanto à linguagem reconhecida, e só — se o problema exige saber qual padrão casou, onde casou e qual foi o casamento mais longo, as três perguntas de um analisador léxico, a passagem exige carregar informação que o teorema não menciona. E a equivalência não sobe de andar: nos autômatos de pilha a resposta será oposta, porque a memória é ilimitada e o argumento de contagem evapora.
1.4 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 toda decorre de uma invariante: cada peça produzida tem a mesma forma externa, seja lá o que tenha dentro. Um fragmento normalizado tem exatamente um estado de entrada e um de saída, distintos; nada chega à entrada e nada parte da saída. São essas duas últimas condições que fazem o trabalho — elas garantem que o fragmento é uma caixa com um fio de cada lado, conectável sem que se saiba o conteúdo.
Os três casos base gastam dois estados cada: a linguagem vazia é o par sem transição, a cadeia vazia é o par ligado por transição vazia, e um símbolo é o par ligado por transição rotulada. A união cria dois estados novos e quatro transições vazias, e os dois são necessários — reaproveitar a entrada de um operando faria essa entrada receber transição, e um laço de repetição no topo desse operando criaria caminhos misturando as alternativas. A concatenação não cria estado nenhum: uma transição vazia da saída do primeiro para a entrada do segundo, e fundir os dois estados, embora correto, quebraria a invariante e traria de volta os casos especiais nos outros cinco casos. A estrela cria dois estados e quatro transições vazias, entre elas o atalho direto da nova entrada para a nova saída, responsável pela repetição de zero ocorrências, e o laço de volta.
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
É a estrela que cria os 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 vazio de uma à outra — o que acontece quando o operando é ele mesmo uma repetição —, fecha-se um ciclo percorrível sem consumir símbolo. É essa situação que obriga o fecho a marcar visitados.
A correção sai por indução estrutural com hipótese dupla, carregando junto “o fragmento é normalizado” e “o fragmento denota a linguagem certa”. O custo é exato: com n folhas e u ocorrências de união e estrela, |Q| = 2n + 2u, no máximo duas saídas por estado. Linear, portanto — mas cuidado com a notação: classes de caracteres não são construtores da teoria. Uma classe é abreviação de união de símbolos, e a construção expande e paga por cada um, a 4k - 2 estados para k símbolos: trinta e oito para uma faixa de dez dígitos, cento e dois para as vinte e seis letras, e a classe negada depende do alfabeto inteiro. As demais formas derivadas também são abreviações — uma-ou-mais reduz-se a uma ocorrência seguida da estrela, zero-ou-uma à união com a cadeia vazia — e implementá-las assim mantém o algoritmo com seis casos.
1.5 Da notação ao texto, e o que a implementação de referência mostra
Falta a etapa que o enunciado esconde e que ocupa metade do trabalho: Thompson opera sobre a árvore da expressão, e expressões chegam como texto. Quem atravessa esse abismo é um analisador de descida recursiva com uma função por nível de precedência — união mais fraca, concatenação no meio, sufixos de repetição mais fortes — cada uma chamando a seguinte, e o átomo voltando ao topo ao encontrar parêntese. Nenhuma função conhece a tabela de precedências, porque a tabela é a ordem das chamadas. Os níveis não são simétricos: a concatenação é justaposição, não tem caractere próprio, e o laço dela precisa de uma lista explícita do que o para — fim do texto, barra vertical e parêntese de fechamento. Sobre erros, três regras: toda falha carrega posição, a primeira falha é preservada, e na dúvida se recusa, porque expressão duvidosa aceita vira autômato que reconhece algo que ninguém pediu.
Na implementação de referência da Peneira, o autômato guarda as vazias em campo separado das demais e expõe o fecho e o movimento por símbolo como operações públicas, porque a determinização vai reusá-las tal como estão:
// 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;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
O confronto que fecha o módulo promove os autômatos desenhados à mão no módulo anterior a gabarito: o gerado a partir da notação da categoria numérica tem de dar o mesmo veredicto que o manual nas treze cadeias do corpus, e as sete a rejeitar é que têm poder de detecção — uma bateria só de positivas aprovaria um autômato que aceita tudo. Resultado medido: treze veredictos iguais, zero divergentes, cento e sessenta e oito estados contra cinco. Somadas as seis categorias léxicas, mil duzentos e noventa e seis estados para uma linguagem minúscula. É esse número que enuncia o problema do próximo módulo.
A sua entrega tem a mesma forma, sobre a linguagem que o seu grupo definiu: tradução automática de expressão regular para autômato não determinístico, incluindo o analisador da sua própria notação, a documentação de quais operadores você suporta e por que excluiu os demais, e a evidência de funcionamento — de preferência no formato do confronto, e não no de uma bateria que só sabe dizer sim.
1.6 Síntese
O não determinismo troca destino único por conjunto de destinos e admite duas leituras equivalentes: adivinhação com oráculo, boa para demonstrar; exploração simultânea, que é a que se implementa. O ganho é conveniência — união custa soma em vez de produto, o raciocínio de retorno some, a tradução fica composicional — e o preço é o custo de execução. As transições vazias existem para colar autômatos sem inspecioná-los por dentro, e obrigam o fecho vazio, cuja terminação depende da marcação de visitados. A equivalência entre os três modelos fala de classes de linguagens e nada sobre tamanho, e apoia-se na finitude do conjunto das partes. Thompson é a ponte automática entre notação e máquina, linear no tamanho da expressão, com as classes de caracteres inflando o resultado por serem abreviações. Voltando à máquina irresponsável da abertura: 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.