1 Determinização e minimização — Guia

A construção de Thompson monta, para o padrão (a|b)*abb, uma máquina de 14 estados, as situações em que pode estar. Ela é não determinística: depois de ler um símbolo, pode estar em vários estados ao mesmo tempo, um peão em cada casa do tabuleiro. As setas, as transições, são de dois tipos: a catraca lê um símbolo, e o corredor, a transição vazia, não lê nada. Ela começa no estado inicial e aceita a cadeia que termina num estado de aceitação.

Os estados ocupados depois de uma leitura formam o conjunto ativo. A simulação o calcula com duas contas: \text{mover}(S, a) reúne os destinos das transições que leem a a partir do conjunto S, e o fecho vazio E(S) acrescenta o que se alcança por transições vazias. Numa máquina determinística, de cada estado sai exatamente uma seta por símbolo. Determinizar troca a de Thompson por uma determinística de 6 estados. O que garante que as duas aceitam as mesmas cadeias?

1.1 Um estado por conjunto, um bloco por comportamento

Vamos chamar de determinizada a máquina nova: cada casa do tabuleiro dela é um conjunto de casas da de Thompson. O alfabeto \Sigma reúne os símbolos escritos em alguma transição.

NotaDefinição — Construção de subconjuntos

Seja N = (Q, \Sigma, \Delta, q_0, F) um autômato finito não determinístico com transições vazias. A construção de subconjuntos produz o autômato finito determinístico D = (Q', \Sigma, \delta', q_0', F') definido por: q_0' = E(\{q_0\}); \delta'(S, a) = E(\text{mover}(S, a)) para S \in Q' e a \in \Sigma; F' = \{\, S \in Q' : S \cap F \neq \emptyset \,\}; e Q' é o menor conjunto de subconjuntos de Q que contém q_0' e é fechado por \delta' — obtido, na prática, expandindo apenas os subconjuntos alcançáveis a partir de q_0', nunca todo \mathcal{P}(Q).

N é a máquina não determinística, e D, a determinizada; o sinal ', lido “linha”, marca o que é de D. Q, \Delta e q_0 são os estados, as transições e o inicial de N, e \delta' e q_0', os de D. F reúne os estados de aceitação, e F', os conjuntos que têm algum deles. \mathcal{P}(Q), “partes de Q”, tem os 2^{|Q|} subconjuntos; “fechado por \delta'” diz que nenhuma seta leva para fora de Q'. Quando nenhum estado de S lê a, o destino é o conjunto vazio; aqui ele é o estado de erro, de onde a máquina não sai.

Depois de cada prefixo, um começo da cadeia, o estado de D é o conjunto dos estados em que N poderia estar. Vale para o prefixo vazio, porque q_0' é o fecho vazio do inicial, e passa ao seguinte porque \delta' repete a simulação. Por essa indução, as duas aceitam as mesmas cadeias sobre \Sigma.

A minimização funde estados equivalentes: dois estados em que nenhuma cadeia, lida a partir de cada um, leva um à aceitação e o outro não. Uma partição divide os estados em blocos, cada estado num só, e o refinamento de partições começa separando os de aceitação dos outros. Cada rodada dá a cada estado uma assinatura, o bloco dele seguido do bloco do destino de cada símbolo, e só deixa juntos os de assinatura igual.

O processo para quando uma rodada não separa ninguém: a partição chegou ao ponto fixo. Como os blocos só se dividem e não passam do número de estados, o ponto fixo chega; nele, dois estados estão juntos exatamente quando são equivalentes. Fundir cada bloco num estado dá a máquina reduzida.

1.2 (a|b)*abb, do primeiro conjunto ao último bloco

A máquina de Thompson (→ no inicial, negrito no de aceitação):

Estado Lendo um símbolo, vai para Por transição vazia, vai para
0 1, com a —
1 — 5
2 3, com b —
3 — 5
4 — 0 e 2
5 — 4 e 7
→ 6 — 4 e 7
7 — 8
8 9, com a —
9 — 10
10 11, com b —
11 — 12
12 13, com b —
13 — —

Do 6, os corredores levam ao 4 e ao 7, do 4 ao 0 e ao 2, do 7 ao 8: q_0' = \{0, 2, 4, 6, 7, 8\}. Com b, só a catraca do 2 serve: E(\{3\}) = \{0, 2, 3, 4, 5, 7, 8\}. Siga até não aparecer conjunto novo.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}") -->|a| D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D0 -->|b| D2("2<br/>{0,2,3,4,5,7,8}")
    D1 -->|a| D1
    D1 -->|b| D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D2 -->|a| D1
    D2 -->|b| D2
    D3 -->|a| D1
    D3 -->|b| D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    D4 -->|a| D1
    D4 -->|b| D2
Figura 1: A máquina determinizada de (a|b)*abb: cada estado é um conjunto, e cada seta vale por uma transição. O estado de erro não está desenhado.

A execução da construção imprime os cinco:

      0 = {0,2,4,6,7,8}
      1 = {0,1,2,4,5,7,8,9,10}
      2 = {0,2,3,4,5,7,8}
      3 = {0,2,3,4,5,7,8,11,12}
      4 = {0,2,3,4,5,7,8,13}

Nenhum conjunto é vazio, mas a execução sempre conta o estado de erro: a determinizada tem 6. A partição inicial é \{0, 1, 2, 3, \text{erro}\} e \{4\}. A primeira rodada separa o 3, cujo b leva ao bloco do 4, e a segunda, o 1, cujo b leva ao 3. A terceira separa o erro, cujo a fica nele, enquanto o do 0 e do 2 vai ao 1. A quarta não separa ninguém; a execução imprime as contagens de blocos 2, 3, 4, 5 e 5. A reduzida tem 5, com o 0 e o 2 fundidos. A máquina mínima, a menor determinística que aceita as mesmas cadeias, sai da mesma fusão sem o estado a que nenhuma cadeia leva, aqui o erro: tem 4.

1.3 O que as contagens desmentem

Os 2^{14} = 16.384 conjuntos possíveis fazem esperar uma máquina maior, mas em (a|b)*abb 14 estados viram 6: os cinco conjuntos alcançados e o estado de erro.

A execução confere que as três máquinas respondem igual às 127 cadeias de até 6 símbolos. Essa bateria de cadeias é evidência, mas a prova é a indução sobre o prefixo e, para a reduzida, o ponto fixo.

1.4 Três contas para conferir

Leia baab na determinizada de (a|b)*abb: por quais estados a leitura passa, que conjunto é o último, e a cadeia é aceita?

0 \to 2 \to 1 \to 1 \to 3. O 3 é \{0, 2, 3, 4, 5, 7, 8, 11, 12\}, onde a máquina de Thompson poderia estar depois de baab. Sem o 13, a cadeia é recusada.

Tire da tabela as linhas 12 e 13 e a transição vazia do 11 ao 12, e faça do 11 o único de aceitação. Quantos estados têm a determinizada, contado o de erro, e a reduzida?

A determinizada tem 5: os três primeiros conjuntos de antes, o de aceitação (\{0, 2, 3, 4, 5, 7, 8, 11\}) e o de erro. A reduzida tem 4, com o 0 e o 2 fundidos, e a mínima, 3.

Uma máquina não determinística tem 4 estados. A determinizada dela pode ter 20, contado o de erro?

Não. Cada estado da determinizada é um subconjunto dos quatro, e há 2^4 = 16, contado o vazio, que é o de erro: no máximo 16.

1.5 Para ir além

No material, “Do conjunto ativo à tabela de consulta” refaz a construção, e “O que a definição deixa ao programa: o conjunto vazio e o alfabeto” trata do estado de erro. “O que a construção garante, e o que ela não promete” mostra a determinizada crescendo, e “Estados que nenhuma continuação separa”, o refinamento parado cedo. “A menor máquina, e o que ela permite comparar” compara padrões, e “Conferir o programa com outra máquina” trata da bateria de cadeias.