%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
S6((6<br/>inicial)) -->|ε| S4((4))
S6 -->|ε| S7((7))
S4 -->|ε| S0((0))
S4 -->|ε| S2((2))
S0 -->|a| S1((1))
S2 -->|b| S3((3))
S1 -->|ε| S5((5))
S3 -->|ε| S5
S5 -->|ε| S4
S5 -->|ε| S7
S7 -->|ε| S8((8))
S8 -->|c| S9(((9)))
1 Autômatos não determinísticos e a construção de Thompson — Guia
Uma máquina que reconhece o padrão (a \mid b)^{*}c tem dez estados, as situações em que ela pode estar. Tem doze transições, as setas de um estado a outro, nove delas sem símbolo. Ninguém a projetou. A construção de Thompson a monta: percorre a árvore do padrão e aplica a cada nó uma regra fixa, sem perguntar o que o padrão quer dizer. Em (a \mid b)^{*}c, a árvore tem seis nós: três folhas, os símbolos, e três operações.
O custo aparece na execução. Antes do primeiro símbolo da cadeia abc, essa máquina ocupa seis estados. Depois do a e do b, ocupa sete. Parece indecisão, como se ela testasse caminhos até um dar certo. Mas os seis saem de uma conta sem sorteio, que você refaz no papel. Aceitar passa a significar que algum percurso, caminho de estado em estado, termina bem. Executar vira carregar um conjunto a cada símbolo.
1.1 Corredores, blocos e conjuntos
Numa estação de metrô, só a catraca cobra ficha. O corredor entre plataformas se cruza de graça. A catraca é a transição que lê símbolo, e o corredor é a transição vazia: a máquina muda de estado sem ler nada. Os estados de aceitação formam o conjunto F. A função de transição \Delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q) admite a transição vazia e devolve um conjunto de estados, talvez vazio.
Cada passageiro ocupa uma plataforma só, mas a máquina ocupa de uma vez todas as que algum deles alcançaria. Onde \Delta devolve o vazio, o percurso acaba, sem estado de erro. A máquina aceita x quando existe um percurso do estado inicial, q_0, a um estado de F que lê x, com corredores intercalados.
Cada nó vira um bloco, ligado ao resto só por dois estados, o de entrada e o de saída. A folha de um símbolo dá dois estados novos e a catraca dele; a da cadeia vazia, dois estados e um corredor. A concatenação, xy, cola dois blocos; a alternância, x|y, oferece os dois; o fecho, x*, repete um.
NotaDefiniçã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).
Nenhum nó acrescenta mais de dois estados. A máquina cresce na proporção da árvore.
Para executar, a simulação carrega o conjunto ativo S_i: os estados onde algum percurso pode estar após ler i símbolos.
NotaDefiniçã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.
NotaDefiniçã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.
1.2 (a \mid b)^{*}c sobre abc, conjunto a conjunto
Só três estados têm catraca: o 0, para a, o 2, para b, e o 8, para c. A simulação imprime o conjunto ativo a cada símbolo:
O inicial é um só, o 6, entrada do bloco do padrão inteiro, e a partida, S_0, é o fecho vazio do 6. Do 6 se vai ao 4 e ao 7, do 4 ao 0 e ao 2, do 7 ao 8. Com o a, só a catraca do 0 serve, e acabam os percursos do 2 e do 8. Os corredores refazem o fecho vazio a partir do 1. O b faz o mesmo pela catraca do 2. Com o c, só serve a do 8, e \{9\} contém o único estado de F.
1.3 O que o conjunto ativo desmente
A máquina não adivinha percurso: a aceitação pede que um exista, e a simulação segue todos. Um percurso que falha não prova recusa, porque a recusa fala de todos. Em (a \mid b)^{*}c, o S_3 de abb reúne a chegada de todos e, sem o 9, prova a recusa.
O fecho vazio vale já na partida. Em a|b sobre b, a partida tem três estados: o inicial e os de entrada das duas folhas. Sem o fecho vazio, sobra o inicial, sem catraca para b, e a cadeia sai recusada.
Carregar o conjunto não constrói máquina determinística. Em (a \mid b)^{*}c sobre ababab, a simulação calcula seis conjuntos após S_0, mas são só dois, alternados, e cada um é descartado depois de usado. Guardá-los como estados, com destino por símbolo, é a determinização, que tem módulo próprio. Ela prova que a máquina determinística e a não determinística reconhecem as mesmas linguagens.
1.4 Três contas para fazer no papel
Decida antes de abrir cada resposta.
Simule a máquina de (a \mid b)^{*}c sobre cb. Que conjunto ativo resta depois de cada símbolo, e a cadeia é aceita?
DicaResposta
Da partida \{6, 4, 7, 8, 0, 2\}, o c só passa pela catraca do 8: \{9\}. Como o 9 não tem transição nenhuma, o b esvazia o conjunto, e a cadeia é recusada.
Aplique as regras da construção a (abc)*, sem fundir estados. Quantos estados e transições a máquina tem, quantas delas vazias, e quantos estados formam a partida?
DicaResposta
Oito estados e nove transições, seis delas corredores. As folhas dão seis estados e três catracas, as concatenações dois corredores, o fecho dois estados e quatro corredores. A partida tem três: os estados de entrada do fecho e da folha a e a saída do fecho.
A máquina que a construção monta para uma árvore de 20 nós pode ter 50 estados, ou um conjunto ativo de 50?
DicaResposta
Não às duas. Nenhum nó acrescenta mais de dois estados, e 20 nós dão no máximo 40. Cada conjunto ativo só tem estados da máquina: não passa do número deles.
1.5 Para ir além
No material, “Não determinismo, ou como juntar máquinas sem abri-las” mostra que em ab|ac o símbolo não decide. “A construção de Thompson, uma peça por nó” traz a origem e o coringa. “A máquina de (a \mid b)^{*}c, montada nó a nó” numera os estados. “Simular é carregar um conjunto a cada caractere” trata da ordem entre mover e fechar. “Quem garante a regra, e quem garante o código” prova a construção. “O tamanho da máquina se conta antes de construí-la” mede o custo.