Autômatos não determinísticos e a construção de Thompson — Atlas

O módulo inteiro em oito peças visuais. Cada uma olha o mesmo conteúdo por um lado: o resumo desenhado, os procedimentos passo a passo, os cartões para treinar de memória, o módulo contado em quadros, o mapa dos tópicos, o painel que junta tudo, a rede de conceitos e a folha para consultar na hora.

Resumo ilustrado

Figura 1: O módulo numa página: a ficha e o corredor, um peão em cada casa, o fecho vazio, o bloco, a tabela de custos, os quatro corredores do fecho, um conjunto por símbolo, quem garante o quê e o tamanho que se conta antes.

Fluxogramas

Cinco procedimentos do módulo. Siga cada um com o lápis, sobre um padrão seu.

Montar a máquina de uma expressão

Uma regra por tipo de nó, e nenhuma decisão de quem monta. A regra de um operador precisa dos blocos dos filhos, e por isso os filhos ficam prontos antes.

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    T["árvore da expressão"]
    V["próximo nó, na<br/>ordem de visita:<br/>filho esquerdo,<br/>filho direito,<br/>o próprio nó"]
    Q{"que tipo<br/>de nó?"}
    F["folha: símbolo,<br/>coringa ou<br/>cadeia vazia<br/>dois estados<br/>novos, e e s;<br/>de e para s, uma<br/>transição com o<br/>rótulo da folha"]
    C["concatenação:<br/>nenhum estado<br/>novo; transição<br/>vazia de s1<br/>para e2; devolve<br/>o bloco (e1, s2)"]
    A["alternância:<br/>dois estados<br/>novos, e e s;<br/>transições vazias<br/>de e para e1 e<br/>para e2, de s1<br/>e de s2 para s"]
    K["fecho: dois<br/>estados novos,<br/>e e s<br/>uma vez ou mais:<br/>e para e1<br/>zero vezes: e para s<br/>de novo: s1 para e1<br/>basta: s1 para s"]
    B["o bloco do nó fica pronto<br/>cada estado novo leva<br/>o próximo número livre"]
    R{"era a<br/>raiz?"}
    FIM["a entrada do bloco da raiz<br/>é o estado inicial; a saída,<br/>o único estado de aceitação"]

    T --> V --> Q
    Q -->|"folha"| F
    Q -->|"operador"| C
    Q -->|"operador"| A
    Q -->|"operador"| K
    F --> B
    C --> B
    A --> B
    K --> B
    B --> R
    R -->|"não"| V
    R -->|"sim"| FIM

Figura 2: A construção de Thompson: a cada visita, o nó recebe a regra do tipo dele, e só no fim o bloco da raiz dá o estado inicial e o de aceitação.

Calcular o fecho vazio de um conjunto

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    I["conjunto de partida S:<br/>anote cada estado de S<br/>como visitado e ponha-o<br/>na pilha e no resultado"]
    P{"a pilha<br/>está vazia?"}
    T["tire o estado de<br/>cima da pilha"]
    X{"falta olhar<br/>alguma transição<br/>vazia que sai dele?"}
    D{"o destino<br/>dela já foi<br/>anotado?"}
    N["anote o destino,<br/>ponha-o na pilha<br/>e no resultado"]
    FIM["o resultado é E(S)"]

    I --> P
    P -->|"não"| T --> X
    X -->|"sim"| D
    D -->|"sim: não volte a ele"| X
    D -->|"não"| N --> X
    X -->|"não"| P
    P -->|"sim"| FIM

Figura 3: O fecho vazio com uma pilha. A anotação de visitado garante o fim da conta: sem ela, em a^{**}, o corredor de ida e o de volta giram sem parar.

Simular a máquina sobre uma cadeia

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    Z["máquina e cadeia<br/>passo zero: o conjunto ativo<br/>é o fecho vazio do<br/>estado inicial"]
    L{"falta ler<br/>algum símbolo?"}
    M["etapa das catracas, o mover:<br/>os destinos, por esse símbolo,<br/>de cada estado do<br/>conjunto ativo"]
    F["etapa do fecho vazio:<br/>o fecho vazio do que o<br/>mover devolveu é o novo<br/>conjunto ativo"]
    V{"o conjunto<br/>ativo ficou<br/>vazio?"}
    R1["recusa: nenhum símbolo<br/>seguinte volta a ocupar<br/>estado algum"]
    Q{"o estado de<br/>aceitação está<br/>no último<br/>conjunto ativo?"}
    AC["aceita"]
    RE["recusa"]

    Z --> L
    L -->|"sim: leia o próximo"| M --> F --> V
    V -->|"não"| L
    V -->|"sim: pode parar de ler"| R1
    L -->|"não"| Q
    Q -->|"sim"| AC
    Q -->|"não"| RE

Figura 4: O passo da simulação tem duas etapas, nesta ordem: as catracas do símbolo lido e, depois, o fecho vazio. O conjunto de partida também passa pelo fecho vazio.

Diagnosticar um defeito com a*

Duas cadeias, a vazia e a, e o traço de cada uma. Três causas dão o mesmo par de respostas, e só o traço as separa.

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    I["rode a máquina de a*<br/>sobre a cadeia vazia e<br/>sobre a cadeia a, e<br/>guarde os traços"]
    V{"a cadeia<br/>vazia é<br/>aceita?"}
    A1{"a cadeia a<br/>é aceita?"}
    A2{"a cadeia a<br/>é aceita?"}
    OK["a ordem e o fecho vazio<br/>inicial estão certos<br/>a falta da transição vazia<br/>“de novo” só a cadeia<br/>aa acusa"]
    T{"o que o traço<br/>mostra?"}
    O["depois do a, só {1}:<br/>a ordem invertida,<br/>fecho vazio antes<br/>do mover"]
    U["o conjunto inicial<br/>é {2, 3}: falta a<br/>transição vazia<br/>“uma vez ou mais”"]
    B["depois do a, {1, 0},<br/>sem o 3: falta a<br/>transição vazia<br/>“basta”"]
    F["o conjunto inicial<br/>é {2}: falta o fecho<br/>vazio do conjunto<br/>inicial"]
    Z["o conjunto inicial<br/>é {2, 0}: o defeito<br/>está na construção,<br/>falta a transição<br/>vazia “zero vezes”"]

    I --> V
    V -->|"sim"| A1
    V -->|"não"| A2
    A1 -->|"sim"| OK
    A1 -->|"não: três suspeitos"| T
    T --> O
    T --> U
    T --> B
    A2 -->|"não"| F
    A2 -->|"sim"| Z

Figura 5: O diagnóstico de a*, na máquina em que o 2 é a entrada do bloco do fecho, o 0 e o 1 são a folha a, e o 3 é a saída.

Escrever o veredito antes de rodar

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    P["um padrão e uma cadeia"]
    R["raciocine sobre a linguagem do padrão,<br/>sem estado, catraca nem corredor"]
    W["escreva o veredito, aceita ou recusa,<br/>antes de rodar o programa"]
    X["rode: o programa monta a máquina,<br/>passa a cadeia e dá a resposta"]
    Q{"a resposta é o veredito?"}
    OK["o caso de teste passa"]
    ERR["o erro está no programa<br/>ou em quem escreveu o caso de teste:<br/>confira os dois"]
    C["copiar a resposta do programa<br/>como veredito faz um registro,<br/>e não um teste"]

    P --> R --> W --> X --> Q
    Q -->|"sim"| OK
    Q -->|"não"| ERR
    X -.->|"o atalho que não serve:<br/>copiar a resposta"| C

Figura 6: Um caso de teste é um padrão, uma cadeia e o veredito. O veredito pensado sem o programa faz um teste; o copiado da resposta dele faz um registro.

Cartões de memória

Leia a frente, diga a resposta em voz alta ou escreva no papel, e só então vire o cartão.

Definição: Autômato finito não determinístico com transições vazias

Um autômato finito não determinístico com transições vazias é uma quíntupla N = (Q, \Sigma, \Delta, q_0, F). Nela, Q é um conjunto finito de estados, \Sigma é um alfabeto finito, q_0 \in Q é o estado inicial e F \subseteq Q é o conjunto dos estados de aceitação. O terceiro componente, \Delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q), é a função de transição: associa a cada par formado por um estado e um símbolo — ou pelo símbolo vazio \varepsilon — um subconjunto de Q, possivelmente vazio.

Definição: Transição vazia

Uma transição vazia é um elemento de \Delta(q, \varepsilon): a máquina passa do estado q para um estado desse conjunto sem ler símbolo algum da entrada, e a posição na cadeia permanece inalterada. A transição está disponível sempre que a máquina esteja em q, independentemente do próximo símbolo.

Definição: Aceitação em máquina não determinística

A máquina N aceita a cadeia x \in \Sigma^* quando x pode ser escrita como y_1 y_2 \ldots y_m, com cada y_i \in \Sigma \cup \{\varepsilon\}, e existe uma sequência de estados r_0, r_1, \ldots, r_m tal que r_0 = q_0, r_i \in \Delta(r_{i-1}, y_i) para todo i, e r_m \in F. Basta que exista uma dessas sequências; as demais, se houver, não precisam terminar em estado de F. A linguagem reconhecida é L(N) = \{\, x \in \Sigma^* : N \text{ aceita } x \,\}.

Definição: Fecho vazio

O fecho vazio de um conjunto S \subseteq Q, denotado E(S), é o menor conjunto que satisfaz S \subseteq E(S) e, para todo q \in E(S), \Delta(q, \varepsilon) \subseteq E(S). Equivalentemente, E(S) é o conjunto de todos os estados alcançáveis a partir de algum estado de S por zero ou mais transições vazias.

Definição: Bloco

Um bloco é um par de estados (e, s) de uma máquina em construção, chamados entrada e saída, tal que o conjunto de cadeias que levam de e a s é exatamente a linguagem denotada pela subexpressão que o bloco representa. Nenhum estado intermediário dos percursos de e a s é estado de aceitação, e uma vez formado, o bloco só se relaciona com o restante da construção pelos seus dois estados distinguidos.

Definição: Casos base da construção

Para o símbolo a \in \Sigma, o bloco é formado por dois estados novos e e s com \Delta(e, a) = \{s\}. Para o coringa, que casa qualquer símbolo de \Sigma, o bloco é formado por dois estados novos com uma transição de e para s rotulada por uma marca distinta de \varepsilon e de todo símbolo de \Sigma, interpretada na simulação como "casa qualquer a \in \Sigma". Para a cadeia vazia \varepsilon, o bloco é formado por dois estados novos com \Delta(e, \varepsilon) = \{s\}.

Definição: Casos compostos da construção

Sejam B_1 = (e_1, s_1) e B_2 = (e_2, s_2) blocos já construídos. A concatenação produz o bloco (e_1, s_2), acrescentando a transição vazia de s_1 para e_2 — nenhum estado novo é criado. A alternância produz o bloco (e, s) com dois estados novos e quatro transições vazias: de e para e_1, de e para e_2, de s_1 para s e de s_2 para s. O fecho de B_1 produz o bloco (e, s) com dois estados novos e quatro transições vazias: de e para e_1 (uma vez ou mais), de e para s (zero vezes), de s_1 para e_1 (de novo) e de s_1 para s (basta).

Definição: Passo da simulação

Dada uma máquina N, define-se \text{mover}(S, a) = \bigcup_{q \in S} \{\, p \in Q : p \in \Delta(q, a) \,\}, que reúne os destinos de todos os estados de S pelo símbolo a \in \Sigma. A simulação de N sobre x = a_1 \ldots a_n produz a sequência de conjuntos S_0 = E(\{q_0\}) e S_i = E(\text{mover}(S_{i-1}, a_i)) para 1 \le i \le n. A máquina aceita a cadeia quando algum estado de S_n pertence a F.

Teorema: Toda expressão regular tem máquina equivalente de tamanho linear

Para toda expressão regular r sobre um alfabeto \Sigma, a aplicação recursiva da definição Casos base da construção e da definição Casos compostos da construção sobre a árvore de r produz um autômato finito não determinístico com transições vazias N tal que L(N) = L(r). O estado inicial de N é a entrada do bloco da raiz e F = \{s\}, em que s é a saída desse bloco: a máquina construída tem exatamente um estado de aceitação. O número de estados de N é O(|r|): cada caso base introduz duas unidades, cada composição introduz no máximo duas, e a concatenação não introduz nenhuma.

Autômato finito não determinístico (AFN)

Máquina com a mesma estrutura da determinística, exceto que um estado pode ter vários destinos pelo mesmo símbolo, nenhum destino, ou destinos alcançados sem consumir símbolo algum. Aceita a cadeia para a qual existe ao menos um caminho até um estado de aceitação, e reconhece a mesma família de linguagens que a versão determinística.

Bloco (na construção de Thompson)

Par de estados, chamados entrada e saída, tal que as cadeias que levam de um ao outro são exatamente as denotadas pela subexpressão que o par representa. Nenhuma transição liga o interior desse par a estados fora dele.

Cadeia vazia

Sequência de comprimento zero, escrita \varepsilon. Pertence ao conjunto de todas as sequências sobre qualquer alfabeto.

Construção de Thompson

Algoritmo que traduz uma expressão regular em máquina não determinística compondo pares de estados por indução na estrutura da expressão, um caso para cada operador.

História em quadros

O módulo contado do começo ao fim, um quadro por vez, na ordem em que o livro avança.

Figura 7: O módulo do começo ao fim, em quinze quadros: a máquina que ninguém desenhou, juntar máquinas sem abri-las, a ficha e o corredor, o percurso que basta existir, o fecho vazio, o bloco, as seis regras, as fusões em ab, os dez estados de (a|b)*c, um conjunto por símbolo, os dois lugares do fecho vazio, simular contra determinizar, os vereditos escritos antes, a definição que já era algoritmo e as doze transições.

Mapa mental

Os tópicos do módulo, do centro para fora, na ordem do livro.

Figura 8: Os tópicos e subtópicos do módulo, em árvore, na ordem do livro, em sentido horário a partir do alto, à direita.

Painel do conhecimento

Conceitos

• Autômato não determinístico com transições vazias: \Delta(q, a) é um conjunto, talvez vazio; há um só estado inicial e um conjunto F de estados de aceitação.
• Transição vazia, o corredor: muda de estado sem ler símbolo.
• Aceitação: existe um percurso que lê a cadeia e termina num estado de F.
• Fecho vazio, E(S): S e tudo o que se alcança por zero ou mais transições vazias.
• Bloco: o par (e, s), uma entrada e uma saída.
• Simulação: um conjunto ativo por símbolo lido, calculado e descartado.

Exemplos

• ab: 4 estados, 3 transições, 1 vazia.
• a|b: 6 estados, 6 transições, 4 vazias; E(\{4\}) = \{4, 0, 2\}.
• a*: 4 estados, 5 transições, 4 vazias.
• (a \mid b)^{*}c: 10 estados, 12 transições, 9 vazias; conjunto de partida de 6 estados.
• Em a*b*, três fusões juntas fazem a máquina aceitar ba.

Diagrama

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    E((2<br/>entrada<br/>do bloco)) -->|"ε: uma vez ou mais"| I0((0))
    I0 -->|a| I1((1))
    I1 -->|"ε: de novo"| I0
    I1 -->|"ε: basta"| S((3<br/>saída<br/>do bloco))
    E -->|"ε: zero vezes"| S

Figura 9: O bloco de a*: a folha a no 0 e no 1, e as quatro transições vazias do fecho, cada uma com o seu nome.

Evidências

• Dezembro de 1951: Stephen Kleene mostra, num memorando, que expressões e autômatos finitos descrevem as mesmas linguagens.
• Junho de 1968: Ken Thompson publica o artigo de que vem o procedimento hoje chamado construção de Thompson.
• Conferido por execução: em 3.736 árvores de 1 a 6 nós, nenhum estado das máquinas da construção tem mais de uma transição que lê símbolo saindo dele.

Referências

• Thompson, o artigo de junho de 1968, com a ficha completa no módulo 02.
• Kleene, o memorando de dezembro de 1951, também contado no módulo 02.
• Aho, Compiladores: princípios, técnicas e ferramentas, 2ª ed., Pearson, 2008.
• Hopcroft, Motwani e Ullman, Introdução à teoria de autômatos, linguagens e computação, Elsevier, 2002.
• Menezes, Linguagens formais e autômatos, 6ª ed., Grupo A, 2011.

Aplicações

• Análise léxica, a parte do compilador que separa o texto de um programa em unidades: é ali que Aho trata a construção.
• .*.*=.*: 14 estados e 19 transições; dobrado o comprimento da linha, o trabalho da simulação dobra, e o do motor com retrocesso fica 2 \times 2 \times 2 = 8 vezes maior.
• Muitas entradas para o mesmo padrão: o trabalho de montar a tabela se reparte entre elas. Uma entrada curta: a simulação termina antes de a tabela ficar pronta.
• No módulo 05, a determinização transforma cada conjunto ativo em estado.

Mapa conceitual

DicaAntes de olhar

Escreva num papel: expressão regular, linguagem da expressão, árvore da expressão, construção de Thompson, casos base, casos compostos, bloco, propriedade das pontas, prova por indução, autômato não determinístico, transição vazia, tabela de custos, simulação, fecho vazio, conjunto ativo, percurso que aceita, bateria, determinização, autômato determinístico. Ligue os conceitos com setas, e escreva em cada seta um verbo que diga qual é a relação. Depois compare com o mapa.

Figura 10: Os conceitos do módulo ligados por frases de ligação. Cada seta, lida da origem ao destino, é uma afirmação do módulo.

Folha de consulta

A máquina, peça por peça

• N = (Q, \Sigma, \Delta, q_0, F), com \Delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)
• \Delta(q, a) é um conjunto; \emptyset é valor legítimo e dispensa o estado de erro
• um só estado inicial, q_0, e o conjunto F de aceitação; a construção dá F com um só estado
• aceita: existe um percurso de q_0 a um estado de F que lê a cadeia; recusa: nenhum existe

Fecho vazio e passo

• E(S): S e o que se alcança por zero ou mais transições vazias
• S_0 = E(\{q_0\})
• S_i = E(\text{mover}(S_{i-1}, a_i)): catracas, depois fecho vazio
• aceita quando algum estado de S_n pertence a F
• conjunto ativo vazio: nenhum símbolo seguinte o ocupa de novo, e pode-se parar de ler

A tabela de custos

Nó da árvore	Estados novos	Transições novas	Vazias
folha: símbolo, coringa ou \varepsilon	2	1	0, ou 1 na folha \varepsilon
concatenação	0	1	1
alternância	2	4	4
fecho	2	4	4

As quatro transições vazias do fecho

• uma vez ou mais: de e para e_1, entra no interior
• zero vezes: de e para s, vai direto à saída
• de novo: de s_1 para e_1, repete o interior
• basta: de s_1 para s, deixa o interior

Contas

• tetos: 2 \times |r| estados e 4 \times |r| transições, com |r| em nós
• ab 4, 3, 1 · a|b 6, 6, 4 · a* 4, 5, 4 (estados, transições, vazias)
• (a \mid b)^{*}c: 6 nós, 10 estados, 12 transições, 9 vazias; maior conjunto ativo, 7
• [a-z]+: 6 caracteres, 51 + 51 + 2 = 104 nós, 206 estados
• 10 estados têm 2^{10} = 1024 subconjuntos; para (a \mid b)^{*}c, a tabela usa 5

Diagnóstico de a*

• a cadeia vazia e a são aceitas: a ordem e o fecho vazio inicial estão certos; a falta da “de novo”, só aa acusa
• a cadeia vazia é aceita e a é recusada: a ordem invertida, a falta da “uma vez ou mais” ou a da “basta”; o traço decide
• as duas são recusadas: falta o fecho vazio do conjunto inicial
• a cadeia vazia é recusada e a é aceita: falta a “zero vezes”, na construção

Erros previsíveis

• “a máquina escolhe o caminho certo”: ela não escolhe; basta existir um percurso, e a simulação segue todos
• “recusar é tão simples quanto aceitar”: aceitar pede um percurso; recusar afirma que nenhum termina num estado de F
• “precisa de estado de erro”: o conjunto vazio já diz que não há transição
• “o não determinismo reconhece mais linguagens”: as duas espécies de máquina reconhecem as mesmas
• “fecho vazio é o que se alcança por pelo menos uma transição vazia”: são zero ou mais, e S \subseteq E(S)
• “simular é determinizar”: a simulação descarta cada conjunto; a determinização o guarda como estado
• “concatenação, alternância e fecho custam o mesmo”: 0, 2 e 2 estados novos
• “fundir estados ligados por transição vazia nunca muda nada”: em a*b*, três fusões fazem aceitar ba