1 Determinização e minimização — Treino
Cada bloco recolhido guarda a resposta de uma pergunta que você responde antes, de memória: escreva, desenhe ou diga em voz alta, e só então abra. Errar antes de abrir faz parte do treino.
1.1 Página em branco
Feche o material e escreva, numa folha em branco, tudo o que você lembra sobre determinização e minimização: as duas construções, os teoremas que as garantem, os exemplos e as contagens. Só então abra a folha abaixo e marque o que ficou de fora e o que você escreveu diferente.
- Cada estado da máquina determinizada é um subconjunto dos estados da não determinística, e as duas aceitam as mesmas cadeias sobre o alfabeto fechado.
- A construção de subconjuntos parte de q_0' = E(\{q_0\}) e calcula \delta'(S, a) = E(\text{mover}(S, a)); F' reúne os conjuntos que têm algum estado de F.
- Só entram os subconjuntos alcançáveis a partir de q_0', nunca todo \mathcal{P}(Q): em
(a|b)*abb, 5 dos 2^{14} = 16.384, e a determinizada tem 6 com o de erro. - O conjunto vazio é o estado de erro.
- A chave do catálogo é a lista ordenada e sem repetição: \{0,2,4\} e \{4,0,2\} são o mesmo conjunto e o mesmo estado.
- O alfabeto fechado \Sigma reúne os símbolos concretos que rotulam alguma transição, sem \varepsilon e sem a marca de coringa; o coringa vira uma transição por cada símbolo de \Sigma.
- Depois de cada prefixo, o estado da determinizada é o conjunto dos estados em que a não determinística poderia estar, e a indução no comprimento do prefixo prova L(D) = L(N) para as cadeias sobre \Sigma.
- Determinizar nem sempre aumenta o número de estados: 14 → 6 em
(a|b)*abb, 84 → 23 em-?[0-9]+, 6 → 5 ema.c. - Quando a aceitação depende de o n-ésimo símbolo contado do fim ser
a, a máquina de Thompson tem 6n + 4 estados, a determinizada 2^n + 2, a reduzida 2^n + 1, e o piso é 2^n: a explosão de estados é da linguagem, e a minimização não a desfaz. - Testemunha é a cadeia que leva um de dois estados à aceitação e o outro não; equivalentes são os estados que nenhuma testemunha separa.
- O refinamento de partições começa por P_0, que separa F de Q \setminus F, e cada rodada junta os estados de mesma assinatura: o bloco do estado e, para cada símbolo, o bloco do destino.
- Os blocos só se dividem e a contagem não passa de |Q|; o processo para na primeira rodada que não separa ninguém, o ponto fixo; nele, dois estados ficam no mesmo bloco se e somente se são equivalentes.
- A minimização nem sempre reduz: em
a.c, a determinizada e a reduzida têm 5 estados. - A máquina reduzida conta sempre o estado de erro; a mínima, só quando alguma seta leva a ele. Em
(a|b)*abb, nenhuma leva: reduzida 5, mínima 4. - O autômato mínimo é único a menos de renomeação de estados, e duas expressões diferentes da mesma linguagem chegam ao mesmo mínimo.
- A bateria de cadeias confere todas as cadeias sobre o alfabeto fechado até um comprimento; para duas máquinas determinísticas sobre o mesmo alfabeto, concordar até a soma dos estados menos 2, contado o de erro, basta.
- Comparadas só as pontas, um erro em cada etapa pode se cancelar: compare nos dois saltos, da máquina de Thompson à determinizada e desta à reduzida.
1.2 Mapa de conceitos
Desenhe de memória os conceitos da lista, ligue com uma seta cada par que tem relação direta e escreva na seta o verbo que diz qual é a relação. Depois compare o seu desenho com a tabela.
- Autômato finito não determinístico
- Construção de subconjuntos
- Alfabeto fechado
- Máquina determinizada
- Estado de erro
- Explosão de estados
- Refinamento de partições
- Assinatura
- Ponto fixo
- Estados equivalentes
- Testemunha
- Máquina reduzida
- Autômato mínimo
- Bateria de cadeias
| De | Relação | Para |
|---|---|---|
| Construção de subconjuntos | recebe o | Autômato finito não determinístico |
| Construção de subconjuntos | produz a | Máquina determinizada |
| Construção de subconjuntos | expande o coringa sobre o | Alfabeto fechado |
| Estado de erro | representa o conjunto vazio na | Máquina determinizada |
| Explosão de estados | persiste na | Máquina reduzida |
| Refinamento de partições | divide os estados da | Máquina determinizada |
| Refinamento de partições | compara em cada rodada a | Assinatura |
| Refinamento de partições | para no | Ponto fixo |
| Refinamento de partições | calcula por aproximações os | Estados equivalentes |
| Ponto fixo | reúne num bloco só os | Estados equivalentes |
| Testemunha | separa os estados que não são | Estados equivalentes |
| Máquina reduzida | tem um estado por bloco do | Ponto fixo |
| Máquina reduzida | conta sempre o | Estado de erro |
| Autômato mínimo | dispensa, quando inacessível, o | Estado de erro |
| Máquina reduzida | iguala, com o erro alcançável, o | Autômato mínimo |
| Bateria de cadeias | é feita sobre o | Alfabeto fechado |
1.3 Não confunda
Conjunto e lista: a construção encontra \{0, 2, 4\} e, mais adiante, os mesmos três estados na ordem 4, 0, 2. São dois estados da determinizada?
Não. Pela definição Construção de subconjuntos, Q' é um conjunto de subconjuntos, e num conjunto a ordem não conta: \{0, 2, 4\} = \{4, 0, 2\}. Uma lista guarda a ordem, e os mesmos três estados cabem em 3 \times 2 \times 1 = 6 listas diferentes. A lista ordenada e sem repetição, 0, 2, 4, é uma só para as seis, e por isso é ela a chave do catálogo. Sem a ordenação, a construção continua finita e a linguagem continua a mesma, mas o mesmo conjunto pode receber até seis números.
Coringa e símbolo do alfabeto: a máquina determinizada de a.c tem uma coluna para o coringa?
Não. Pela definição Alfabeto fechado da determinização, \Sigma reúne os símbolos concretos que rotulam alguma transição, e a marca de coringa não entra nele: a transição de coringa passa a valer por uma transição por cada símbolo de \Sigma. Em a.c, \Sigma = \{a, c\}, e a tabela da determinizada tem duas colunas, a e c. Do conjunto \{1, 2\}, de onde sai a transição de coringa, a construção vai a \{3, 4\} lendo a e também lendo c.
Explosão de estados e desperdício da construção: na linguagem em que o oitavo símbolo contado do fim é a, a determinizada tem 258 estados. A construção de subconjuntos criou estados à toa?
Não. Estados criados à toa seriam equivalentes a outros, e a minimização os fundiria; a reduzida tem 257, um estado a menos. As 2^8 = 256 cadeias de a e b com oito símbolos são prefixos dois a dois distinguíveis, e por isso toda máquina determinística dessa linguagem tem pelo menos 256 estados. O crescimento vem do que a linguagem exige lembrar, e não do algoritmo.
Ponto fixo e contagem esperada: a máquina mínima de (a|b)*abb tem 4 estados. Parar o refinamento sobre a determinizada de 6 estados quando a contagem chegar a 4 é parar no ponto fixo?
Não. O ponto fixo é a primeira rodada em que P_{i+1} = P_i, e só nele cada bloco reúne exatamente estados equivalentes. Com o estado de erro na conta, as contagens são 2, 3, 4, 5, 5. A contagem chega a 4 com os blocos \{0, 2, \text{erro}\}, \{1\}, \{3\} e \{4\}, e a rodada seguinte ainda separa o erro: o a dele fica nele, e o do 0 e o do 2 vão ao 1. Parar pela contagem coincide com o ponto fixo só quando o número esperado é o do ponto fixo, aqui 5.
1.4 Perguntas em três níveis
1.4.1 Lembrar
Como a construção de subconjuntos define, a partir de N, o autômato determinístico D?
Definiçã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).
Quando dois estados p e q de um autômato finito determinístico são equivalentes?
Definição — Estados equivalentes (indistinguibilidade).
Dois estados p, q \in Q de um autômato finito determinístico (Q, \Sigma, \delta, q_0, F) são equivalentes (ou indistinguíveis) quando, para toda cadeia w \in \Sigma^*, \hat\delta(p, w) \in F se e somente se \hat\delta(q, w) \in F — em que \hat\delta estende \delta a cadeias da forma usual. Ou seja: nenhuma cadeia, por mais longa que seja, os separa quanto à aceitação.
O que afirma o teorema de unicidade do autômato mínimo, e que hipótese ele faz sobre D?
Teorema — Unicidade do autômato mínimo.
Seja D um autômato finito determinístico sem estados inacessíveis a partir de q_0. O autômato obtido fundindo, em D, cada classe de estados equivalentes segundo a definição Estados equivalentes (indistinguibilidade) num único estado reconhece L(D), tem o menor número de estados entre todos os autômatos determinísticos que reconhecem L(D), e é único a menos de renomeação de estados.
1.4.2 Explicar
Por que a construção de subconjuntos aplica o fecho vazio depois de cada \text{mover}, e não só ao estado inicial?
Sem o fecho vazio, o conjunto perde os estados que as transições vazias alcançam depois do símbolo, e o estado da determinizada deixa de ser o conjunto dos estados em que a não determinística poderia estar. Em (a|b)*abb, de q_0' = \{0, 2, 4, 6, 7, 8\}, as transições que leem a dão \{1, 9\}. Nem o 1 nem o 9 leem b, e sem o fecho vazio o b seguinte levaria ao conjunto vazio: abb, que está na linguagem, seria recusada. Com o fecho vazio, \{1, 9\} vira \{0, 1, 2, 4, 5, 7, 8, 9, 10\}, e o 10 lê b.
Por que o refinamento de partições sempre para, e por que, depois da rodada que não separa ninguém, nenhuma outra mudaria a partição?
O primeiro item da assinatura é o bloco do próprio estado, e por isso dois estados de blocos diferentes nunca voltam a ficar juntos: a rodada só divide. A contagem nunca diminui e não passa de |Q|, já que nenhum bloco fica vazio; logo alguma rodada não separa ninguém. Nela, P_{i+1} = P_i, e a rodada seguinte calcularia as mesmas assinaturas sobre a mesma partição. Em (a|b)*abb, com 6 estados, as contagens 2, 3, 4, 5, 5 param na quarta rodada.
Uma máquina determinística de 6 estados e outra de 5, as duas lendo os mesmos símbolos e contado o de erro, concordam em todas as cadeias de até 9 símbolos. Por que concordam, então, em todas as cadeias?
Ponha as linhas das duas numa tabela só, de 11 estados, e rode o refinamento, que não usa o estado inicial. A contagem começa em no máximo 2, cresce a cada rodada que separa e não passa de 11: no máximo 11 - 2 = 9 rodadas separam. A rodada r separa dois estados com uma testemunha de r símbolos. Uma cadeia em que as máquinas discordam é testemunha dos dois estados iniciais. Sem nenhuma até 9 símbolos, nenhuma rodada separa os dois, e eles chegam ao ponto fixo no mesmo bloco: são equivalentes.
1.4.3 Aplicar
Uma máquina não determinística sem transições vazias, sobre o alfabeto \{a, b\}, tem os estados 0, 1 e 2, inicial 0 e o 2 como único de aceitação. As transições são estas, e não há outras: do 0 ao 0, com a e com b; do 0 ao 1, com a; do 1 ao 2, com a e com b. Ela aceita as cadeias cujo penúltimo símbolo é a. Que conjuntos a construção de subconjuntos produz, quantos estados têm a determinizada e a reduzida, contado o de erro, e quantos tem a mínima?
Os quatro conjuntos formados pelo 0 e por um subconjunto qualquer de \{1, 2\}: \{0\}, \{0, 1\}, \{0, 2\} e \{0, 1, 2\}. Nenhum é vazio, e com o estado de erro a determinizada tem 5. As contagens do refinamento são 2, 4, 5, 5, e a reduzida também tem 5. Nenhuma seta leva ao erro, e a mínima tem 4, o piso 2^2.
Para -?[0-9]+, sobre um alfabeto fechado de 11 símbolos, a determinizada tem 23 estados, e a reduzida, 4, as duas contando o de erro. Pela regra da soma dos estados menos 2, até que comprimento basta uma bateria de cadeias para que a concordância das duas máquinas valha para todas as cadeias sobre esse alfabeto, e quantas cadeias desse comprimento exato ela teria?
Até o comprimento 23 + 4 - 2 = 25. Cada um dos 25 lugares da cadeia recebe um dos 11 símbolos, e as cadeias de comprimento 25 são 11^{25}, mais de 10^{26}.
1.5 Cartões
Leia a frente, diga ou escreva a definição de memória e só então abra o cartão.
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).
O alfabeto \Sigma usado na definição Construção de subconjuntos é o conjunto dos símbolos concretos que rotulam alguma transição de N, em qualquer ordem fixa — nem o símbolo vazio \varepsilon nem a marca de coringa entram nele diretamente. Uma transição de coringa em N passa a corresponder, na construção de subconjuntos, a uma transição por cada símbolo de \Sigma: o coringa deixa de ser um símbolo à parte e se torna uma abreviação decidida no momento em que \Sigma é fechado.
Para todo autômato finito não determinístico com transições vazias N, o autômato determinístico D obtido pela definição Construção de subconjuntos satisfaz L(D) = L(N). A prova segue por indução no comprimento do prefixo consumido: após ler um prefixo qualquer da entrada, o estado em que D se encontra é exatamente o conjunto de estados em que N poderia estar — vale para o prefixo vazio, porque q_0' = E(\{q_0\}), e se vale para um prefixo, vale para ele mais um símbolo, porque é assim que \delta' é definida. A cadeia inteira é o caso particular em que o prefixo é a cadeia toda, e D aceita exatamente quando algum estado de F pertence ao conjunto — que é o critério de F'.
Dois estados p, q \in Q de um autômato finito determinístico (Q, \Sigma, \delta, q_0, F) são equivalentes (ou indistinguíveis) quando, para toda cadeia w \in \Sigma^*, \hat\delta(p, w) \in F se e somente se \hat\delta(q, w) \in F — em que \hat\delta estende \delta a cadeias da forma usual. Ou seja: nenhuma cadeia, por mais longa que seja, os separa quanto à aceitação.
O refinamento de partições calcula a definição Estados equivalentes (indistinguibilidade) por aproximações sucessivas. A partição inicial P_0 separa F de Q \setminus F. Dada uma partição P_i, a assinatura de um estado q sob P_i é a sequência formada pelo bloco de P_i que contém q seguido, para cada símbolo a \in \Sigma, do bloco de P_i que contém \delta(q, a). A partição P_{i+1} agrupa em um mesmo bloco exatamente os estados de P_i com a mesma assinatura sob P_i. O processo para na primeira rodada em que P_{i+1} = P_i.
A sequência P_0, P_1, P_2, \ldots da definição Refinamento de partições é monótona — todo bloco de P_{i+1} está contido em algum bloco de P_i — e por isso o número de blocos nunca decresce; como ele é limitado por |Q|, existe k tal que P_{k+1} = P_k. Nesse ponto fixo, dois estados estão no mesmo bloco de P_k se e somente se são equivalentes segundo a definição Estados equivalentes (indistinguibilidade).
Seja D um autômato finito determinístico sem estados inacessíveis a partir de q_0. O autômato obtido fundindo, em D, cada classe de estados equivalentes segundo a definição Estados equivalentes (indistinguibilidade) num único estado reconhece L(D), tem o menor número de estados entre todos os autômatos determinísticos que reconhecem L(D), e é único a menos de renomeação de estados.
Pedaço de máquina em construção com exatamente um estado por onde se entra e um por onde se sai, a entrada do bloco e a saída do bloco, tal que as cadeias que levam de um ao outro são exatamente as que o pedaço correspondente da expressão denota. Nenhum estado do meio desses percursos é de aceitação, e o pedaço só se liga ao resto da máquina por esses dois estados.
Cada grupo de uma partição dos estados de uma máquina, isto é, de uma divisão desses estados em grupos, com cada estado em exatamente um grupo. Refinar a partição é dividir grupos dela em grupos menores; a minimização faz isso rodada a rodada, até nenhum grupo se dividir mais.
Procedimento que traduz uma expressão regular em máquina não determinística, percorrendo a árvore da expressão e montando, para cada nó, um bloco, um pedaço de máquina com um estado de entrada e um de saída: há uma regra para cada caso base e uma para cada operador. A máquina que sai dele aceita exatamente as cadeias que a expressão denota e tem no máximo dois estados por nó da árvore. O nome vem de Ken Thompson, do artigo que ele publicou em junho de 1968.
Transformação que troca uma máquina não determinística por uma determinística que aceita as mesmas cadeias; o procedimento que a faz é a construção de subconjuntos. O número de estados pode diminuir ou aumentar, e no máximo chega a 2^n, o resultado de multiplicar n números 2 entre si, quando a máquina de partida tem n estados.
Estado que não é de aceitação e do qual a máquina não sai mais: todas as transições que saem dele voltam para ele mesmo. A cadeia que cai nele é recusada no fim da leitura, mas a cadeia que só termina cedo demais é recusada sem passar por ele, porque a leitura acaba num estado que não aceita. Também se chama sumidouro, e os desenhos costumam deixá-lo de fora, junto com as setas que levam a ele.
Resultado sobre toda linguagem regular: existe um comprimento tal que cada cadeia da linguagem com pelo menos esse comprimento se divide em três trechos, com pelo menos um símbolo no do meio e com os dois primeiros, juntos, não mais compridos que esse comprimento. Nessa divisão, repetir o trecho do meio qualquer número de vezes, zero inclusive, mantém a cadeia na linguagem. Usa-se para provar que uma linguagem não é regular: supõe-se que ela é regular, aplica-se o lema e chega-se a uma cadeia que deveria estar na linguagem e não está. Ele nunca prova que uma linguagem é regular.
Transformação que produz, a partir de uma máquina determinística sem estados inacessíveis desde o inicial, a de menor número de estados que reconhece a mesma linguagem. O resultado é único a menos de renomeação dos estados.
Representação da função de transição como matriz indexada por estado e por símbolo, em que cada célula guarda o destino. Dá acesso em tempo constante e ocupa espaço proporcional ao produto das duas dimensões, esteja a célula ocupada ou não.
1.6 Tutor
Copie o texto abaixo e cole-o como primeira mensagem de uma conversa nova com um assistente de inteligência artificial. Ele passa a trabalhar só com o conteúdo deste módulo e oferece quatro modos: explicar com as suas palavras, ser examinado, despejar tudo numa página em branco e separar conceitos parecidos. Numa conversa longa o assistente perde as regras de vista; passadas umas trinta trocas, cole o texto de novo.
# TUTOR DE ESTUDO
Você vai me ajudar a estudar "Determinização e minimização", módulo 05 de Compiladores e Linguagens Formais e Autômatos. O material de referência está no fim desta mensagem, entre as linhas "INÍCIO DO MATERIAL" e "FIM DO MATERIAL", e ele é a autoridade desta conversa.
## Regras
1. Responda com base no material. Se eu perguntar algo que ele não cobre, diga isso primeiro; se responder mesmo assim, marque o que veio de fora dele.
2. Ao corrigir uma definição, use a do material, palavra por palavra.
3. Não invente data, autor, obra, número ou episódio histórico. O que o material não traz, você não afirma.
4. Uma pergunta por vez. Espere a minha resposta antes de dar a sua.
5. Não me dê a resposta antes de eu tentar. Se eu pedir, dê uma pista primeiro; a resposta, só se eu pedir de novo.
6. Se eu colar uma questão de lista, de questionário ou de trabalho que vale nota, não a resolva: diga por quê e me proponha uma pergunta parecida, sobre outro caso.
7. Não escreva código para o meu projeto.
## Modos
Comece me perguntando qual destes quatro modos eu quero, e troque quando eu pedir.
- EXPLICAR: eu explico um conceito do material com as minhas palavras, como para alguém que nunca o viu. Você aponta o que faltou, o que ficou vago e o que contradiz o material, citando o trecho. Não reescreva a minha explicação: pergunte até eu mesmo consertar.
- EXAMINADOR: você me faz perguntas sobre o material, uma por vez, alternando três tipos: o que é (lembrar), por que é assim (explicar) e o que acontece num caso que o material não resolveu (aplicar). Depois de cada resposta, diga o que está certo, o que está errado e por quê. A cada dez perguntas, liste os conceitos em que errei.
- PÁGINA EM BRANCO: eu escrevo tudo o que lembro do módulo, sem consultar nada. Você compara com o material e lista, na ordem dele, o que faltou e o que escrevi errado.
- NÃO CONFUNDA: você escolhe dois conceitos do material que se parecem e me pergunta o que os separa; depois me dá um caso concreto e pergunta qual dos dois se aplica a ele.
===== INÍCIO DO MATERIAL =====
## O guia do módulo
# 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?
## 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.
**Definiçã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**.
## `(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.
A execução da construção imprime os cinco:
```text
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.
## 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.
## 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?
**Resposta**
$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?
**Resposta**
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?
**Resposta**
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.
## 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.
## Definições e resultados formais, palavra por palavra
### Definiçã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)$.
### Definição: Alfabeto fechado da determinização
O alfabeto $\Sigma$ usado na definição *Construção de subconjuntos* é o conjunto dos símbolos concretos que rotulam alguma transição de $N$, em qualquer ordem fixa — nem o símbolo vazio $\varepsilon$ nem a marca de coringa entram nele diretamente. Uma transição de coringa em $N$ passa a corresponder, na construção de subconjuntos, a uma transição por **cada** símbolo de $\Sigma$: o coringa deixa de ser um símbolo à parte e se torna uma abreviação decidida no momento em que $\Sigma$ é fechado.
### Teorema: Equivalência entre autômato não determinístico e determinístico por construção
Para todo autômato finito não determinístico com transições vazias $N$, o autômato determinístico $D$ obtido pela definição *Construção de subconjuntos* satisfaz $L(D) = L(N)$. A prova segue por indução no comprimento do prefixo consumido: após ler um prefixo qualquer da entrada, o estado em que $D$ se encontra é exatamente o conjunto de estados em que $N$ poderia estar — vale para o prefixo vazio, porque $q_0' = E(\{q_0\})$, e se vale para um prefixo, vale para ele mais um símbolo, porque é assim que $\delta'$ é definida. A cadeia inteira é o caso particular em que o prefixo é a cadeia toda, e $D$ aceita exatamente quando algum estado de $F$ pertence ao conjunto — que é o critério de $F'$.
### Definição: Estados equivalentes (indistinguibilidade)
Dois estados $p, q \in Q$ de um autômato finito determinístico $(Q, \Sigma, \delta, q_0, F)$ são equivalentes (ou indistinguíveis) quando, para toda cadeia $w \in \Sigma^*$, $\hat\delta(p, w) \in F$ se e somente se $\hat\delta(q, w) \in F$ — em que $\hat\delta$ estende $\delta$ a cadeias da forma usual. Ou seja: nenhuma cadeia, por mais longa que seja, os separa quanto à aceitação.
### Definição: Refinamento de partições
O refinamento de partições calcula a definição *Estados equivalentes (indistinguibilidade)* por aproximações sucessivas. A partição inicial $P_0$ separa $F$ de $Q \setminus F$. Dada uma partição $P_i$, a **assinatura** de um estado $q$ sob $P_i$ é a sequência formada pelo bloco de $P_i$ que contém $q$ seguido, para cada símbolo $a \in \Sigma$, do bloco de $P_i$ que contém $\delta(q, a)$. A partição $P_{i+1}$ agrupa em um mesmo bloco exatamente os estados de $P_i$ com a mesma assinatura sob $P_i$. O processo para na primeira rodada em que $P_{i+1} = P_i$.
### Teorema: Correção do refinamento de partições
A sequência $P_0, P_1, P_2, \ldots$ da definição *Refinamento de partições* é monótona — todo bloco de $P_{i+1}$ está contido em algum bloco de $P_i$ — e por isso o número de blocos nunca decresce; como ele é limitado por $|Q|$, existe $k$ tal que $P_{k+1} = P_k$. Nesse ponto fixo, dois estados estão no mesmo bloco de $P_k$ se e somente se são equivalentes segundo a definição *Estados equivalentes (indistinguibilidade)*.
### Teorema: Unicidade do autômato mínimo
Seja $D$ um autômato finito determinístico sem estados inacessíveis a partir de $q_0$. O autômato obtido fundindo, em $D$, cada classe de estados equivalentes segundo a definição *Estados equivalentes (indistinguibilidade)* num único estado reconhece $L(D)$, tem o menor número de estados entre todos os autômatos determinísticos que reconhecem $L(D)$, e é único a menos de renomeação de estados.
## Termos do módulo
- **Bloco (na construção de Thompson)**: Pedaço de máquina em construção com exatamente um estado por onde se entra e um por onde se sai, a entrada do bloco e a saída do bloco, tal que as cadeias que levam de um ao outro são exatamente as que o pedaço correspondente da expressão denota. Nenhum estado do meio desses percursos é de aceitação, e o pedaço só se liga ao resto da máquina por esses dois estados.
- **Bloco (de uma partição)**: Cada grupo de uma partição dos estados de uma máquina, isto é, de uma divisão desses estados em grupos, com cada estado em exatamente um grupo. Refinar a partição é dividir grupos dela em grupos menores; a minimização faz isso rodada a rodada, até nenhum grupo se dividir mais.
- **Construção de Thompson**: Procedimento que traduz uma expressão regular em máquina não determinística, percorrendo a árvore da expressão e montando, para cada nó, um bloco, um pedaço de máquina com um estado de entrada e um de saída: há uma regra para cada caso base e uma para cada operador. A máquina que sai dele aceita exatamente as cadeias que a expressão denota e tem no máximo dois estados por nó da árvore. O nome vem de Ken Thompson, do artigo que ele publicou em junho de 1968.
- **Determinização**: Transformação que troca uma máquina não determinística por uma determinística que aceita as mesmas cadeias; o procedimento que a faz é a construção de subconjuntos. O número de estados pode diminuir ou aumentar, e no máximo chega a $2^n$, o resultado de multiplicar $n$ números 2 entre si, quando a máquina de partida tem $n$ estados.
- **Estado de erro**: Estado que não é de aceitação e do qual a máquina não sai mais: todas as transições que saem dele voltam para ele mesmo. A cadeia que cai nele é recusada no fim da leitura, mas a cadeia que só termina cedo demais é recusada sem passar por ele, porque a leitura acaba num estado que não aceita. Também se chama sumidouro, e os desenhos costumam deixá-lo de fora, junto com as setas que levam a ele.
- **Lema do bombeamento**: Resultado sobre toda linguagem regular: existe um comprimento tal que cada cadeia da linguagem com pelo menos esse comprimento se divide em três trechos, com pelo menos um símbolo no do meio e com os dois primeiros, juntos, não mais compridos que esse comprimento. Nessa divisão, repetir o trecho do meio qualquer número de vezes, zero inclusive, mantém a cadeia na linguagem. Usa-se para provar que uma linguagem não é regular: supõe-se que ela é regular, aplica-se o lema e chega-se a uma cadeia que deveria estar na linguagem e não está. Ele nunca prova que uma linguagem é regular.
- **Minimização**: Transformação que produz, a partir de uma máquina determinística sem estados inacessíveis desde o inicial, a de menor número de estados que reconhece a mesma linguagem. O resultado é único a menos de renomeação dos estados.
- **Tabela de transição**: Representação da função de transição como matriz indexada por estado e por símbolo, em que cada célula guarda o destino. Dá acesso em tempo constante e ocupa espaço proporcional ao produto das duas dimensões, esteja a célula ocupada ou não.
## Revisão do módulo, com as respostas
## Página em branco
Feche o material e escreva, numa folha em branco, tudo o que você lembra sobre determinização e minimização: as duas construções, os teoremas que as garantem, os exemplos e as contagens. Só então abra a folha abaixo e marque o que ficou de fora e o que você escreveu diferente.
**A folha do módulo**
- Cada estado da máquina determinizada é um subconjunto dos estados da não determinística, e as duas aceitam as mesmas cadeias sobre o alfabeto fechado.
- A construção de subconjuntos parte de $q_0' = E(\{q_0\})$ e calcula $\delta'(S, a) = E(\text{mover}(S, a))$; $F'$ reúne os conjuntos que têm algum estado de $F$.
- Só entram os subconjuntos alcançáveis a partir de $q_0'$, nunca todo $\mathcal{P}(Q)$: em `(a|b)*abb`, 5 dos $2^{14} = 16.384$, e a determinizada tem 6 com o de erro.
- O conjunto vazio é o estado de erro.
- A chave do catálogo é a lista ordenada e sem repetição: $\{0,2,4\}$ e $\{4,0,2\}$ são o mesmo conjunto e o mesmo estado.
- O alfabeto fechado $\Sigma$ reúne os símbolos concretos que rotulam alguma transição, sem $\varepsilon$ e sem a marca de coringa; o coringa vira uma transição por cada símbolo de $\Sigma$.
- Depois de cada prefixo, o estado da determinizada é o conjunto dos estados em que a não determinística poderia estar, e a indução no comprimento do prefixo prova $L(D) = L(N)$ para as cadeias sobre $\Sigma$.
- Determinizar nem sempre aumenta o número de estados: 14 → 6 em `(a|b)*abb`, 84 → 23 em `-?[0-9]+`, 6 → 5 em `a.c`.
- Quando a aceitação depende de o $n$-ésimo símbolo contado do fim ser `a`, a máquina de Thompson tem $6n + 4$ estados, a determinizada $2^n + 2$, a reduzida $2^n + 1$, e o piso é $2^n$: a explosão de estados é da linguagem, e a minimização não a desfaz.
- Testemunha é a cadeia que leva um de dois estados à aceitação e o outro não; equivalentes são os estados que nenhuma testemunha separa.
- O refinamento de partições começa por $P_0$, que separa $F$ de $Q \setminus F$, e cada rodada junta os estados de mesma assinatura: o bloco do estado e, para cada símbolo, o bloco do destino.
- Os blocos só se dividem e a contagem não passa de $|Q|$; o processo para na primeira rodada que não separa ninguém, o ponto fixo; nele, dois estados ficam no mesmo bloco se e somente se são equivalentes.
- A minimização nem sempre reduz: em `a.c`, a determinizada e a reduzida têm 5 estados.
- A máquina reduzida conta sempre o estado de erro; a mínima, só quando alguma seta leva a ele. Em `(a|b)*abb`, nenhuma leva: reduzida 5, mínima 4.
- O autômato mínimo é único a menos de renomeação de estados, e duas expressões diferentes da mesma linguagem chegam ao mesmo mínimo.
- A bateria de cadeias confere todas as cadeias sobre o alfabeto fechado até um comprimento; para duas máquinas determinísticas sobre o mesmo alfabeto, concordar até a soma dos estados menos 2, contado o de erro, basta.
- Comparadas só as pontas, um erro em cada etapa pode se cancelar: compare nos dois saltos, da máquina de Thompson à determinizada e desta à reduzida.
## Mapa de conceitos
Desenhe de memória os conceitos da lista, ligue com uma seta cada par que tem relação direta e escreva na seta o verbo que diz qual é a relação. Depois compare o seu desenho com a tabela.
- Autômato finito não determinístico
- Construção de subconjuntos
- Alfabeto fechado
- Máquina determinizada
- Estado de erro
- Explosão de estados
- Refinamento de partições
- Assinatura
- Ponto fixo
- Estados equivalentes
- Testemunha
- Máquina reduzida
- Autômato mínimo
- Bateria de cadeias
**As relações**
| De | Relação | Para |
| --- | --- | --- |
| Construção de subconjuntos | recebe o | Autômato finito não determinístico |
| Construção de subconjuntos | produz a | Máquina determinizada |
| Construção de subconjuntos | expande o coringa sobre o | Alfabeto fechado |
| Estado de erro | representa o conjunto vazio na | Máquina determinizada |
| Explosão de estados | persiste na | Máquina reduzida |
| Refinamento de partições | divide os estados da | Máquina determinizada |
| Refinamento de partições | compara em cada rodada a | Assinatura |
| Refinamento de partições | para no | Ponto fixo |
| Refinamento de partições | calcula por aproximações os | Estados equivalentes |
| Ponto fixo | reúne num bloco só os | Estados equivalentes |
| Testemunha | separa os estados que não são | Estados equivalentes |
| Máquina reduzida | tem um estado por bloco do | Ponto fixo |
| Máquina reduzida | conta sempre o | Estado de erro |
| Autômato mínimo | dispensa, quando inacessível, o | Estado de erro |
| Máquina reduzida | iguala, com o erro alcançável, o | Autômato mínimo |
| Bateria de cadeias | é feita sobre o | Alfabeto fechado |
## Não confunda
**Conjunto** e **lista**: a construção encontra $\{0, 2, 4\}$ e, mais adiante, os mesmos três estados na ordem 4, 0, 2. São dois estados da determinizada?
**Resposta**
Não. Pela definição *Construção de subconjuntos*, $Q'$ é um conjunto de subconjuntos, e num conjunto a ordem não conta: $\{0, 2, 4\} = \{4, 0, 2\}$. Uma lista guarda a ordem, e os mesmos três estados cabem em $3 \times 2 \times 1 = 6$ listas diferentes. A lista ordenada e sem repetição, 0, 2, 4, é uma só para as seis, e por isso é ela a chave do catálogo. Sem a ordenação, a construção continua finita e a linguagem continua a mesma, mas o mesmo conjunto pode receber até seis números.
**Coringa** e **símbolo do alfabeto**: a máquina determinizada de `a.c` tem uma coluna para o coringa?
**Resposta**
Não. Pela definição *Alfabeto fechado da determinização*, $\Sigma$ reúne os símbolos concretos que rotulam alguma transição, e a marca de coringa não entra nele: a transição de coringa passa a valer por uma transição por cada símbolo de $\Sigma$. Em `a.c`, $\Sigma = \{a, c\}$, e a tabela da determinizada tem duas colunas, `a` e `c`. Do conjunto $\{1, 2\}$, de onde sai a transição de coringa, a construção vai a $\{3, 4\}$ lendo `a` e também lendo `c`.
**Explosão de estados** e **desperdício da construção**: na linguagem em que o oitavo símbolo contado do fim é `a`, a determinizada tem 258 estados. A construção de subconjuntos criou estados à toa?
**Resposta**
Não. Estados criados à toa seriam equivalentes a outros, e a minimização os fundiria; a reduzida tem 257, um estado a menos. As $2^8 = 256$ cadeias de `a` e `b` com oito símbolos são prefixos dois a dois distinguíveis, e por isso toda máquina determinística dessa linguagem tem pelo menos 256 estados. O crescimento vem do que a linguagem exige lembrar, e não do algoritmo.
**Ponto fixo** e **contagem esperada**: a máquina mínima de `(a|b)*abb` tem 4 estados. Parar o refinamento sobre a determinizada de 6 estados quando a contagem chegar a 4 é parar no ponto fixo?
**Resposta**
Não. O ponto fixo é a primeira rodada em que $P_{i+1} = P_i$, e só nele cada bloco reúne exatamente estados equivalentes. Com o estado de erro na conta, as contagens são 2, 3, 4, 5, 5. A contagem chega a 4 com os blocos $\{0, 2, \text{erro}\}$, $\{1\}$, $\{3\}$ e $\{4\}$, e a rodada seguinte ainda separa o erro: o `a` dele fica nele, e o do 0 e o do 2 vão ao 1. Parar pela contagem coincide com o ponto fixo só quando o número esperado é o do ponto fixo, aqui 5.
## Perguntas em três níveis
### Lembrar
Como a construção de subconjuntos define, a partir de $N$, o autômato determinístico $D$?
**Resposta**
Definiçã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)$.
Quando dois estados $p$ e $q$ de um autômato finito determinístico são equivalentes?
**Resposta**
Definição — Estados equivalentes (indistinguibilidade).
Dois estados $p, q \in Q$ de um autômato finito determinístico $(Q, \Sigma, \delta, q_0, F)$ são equivalentes (ou indistinguíveis) quando, para toda cadeia $w \in \Sigma^*$, $\hat\delta(p, w) \in F$ se e somente se $\hat\delta(q, w) \in F$ — em que $\hat\delta$ estende $\delta$ a cadeias da forma usual. Ou seja: nenhuma cadeia, por mais longa que seja, os separa quanto à aceitação.
O que afirma o teorema de unicidade do autômato mínimo, e que hipótese ele faz sobre $D$?
**Resposta**
Teorema — Unicidade do autômato mínimo.
Seja $D$ um autômato finito determinístico sem estados inacessíveis a partir de $q_0$. O autômato obtido fundindo, em $D$, cada classe de estados equivalentes segundo a definição *Estados equivalentes (indistinguibilidade)* num único estado reconhece $L(D)$, tem o menor número de estados entre todos os autômatos determinísticos que reconhecem $L(D)$, e é único a menos de renomeação de estados.
### Explicar
Por que a construção de subconjuntos aplica o fecho vazio depois de cada $\text{mover}$, e não só ao estado inicial?
**Resposta**
Sem o fecho vazio, o conjunto perde os estados que as transições vazias alcançam depois do símbolo, e o estado da determinizada deixa de ser o conjunto dos estados em que a não determinística poderia estar. Em `(a|b)*abb`, de $q_0' = \{0, 2, 4, 6, 7, 8\}$, as transições que leem `a` dão $\{1, 9\}$. Nem o 1 nem o 9 leem `b`, e sem o fecho vazio o `b` seguinte levaria ao conjunto vazio: `abb`, que está na linguagem, seria recusada. Com o fecho vazio, $\{1, 9\}$ vira $\{0, 1, 2, 4, 5, 7, 8, 9, 10\}$, e o 10 lê `b`.
Por que o refinamento de partições sempre para, e por que, depois da rodada que não separa ninguém, nenhuma outra mudaria a partição?
**Resposta**
O primeiro item da assinatura é o bloco do próprio estado, e por isso dois estados de blocos diferentes nunca voltam a ficar juntos: a rodada só divide. A contagem nunca diminui e não passa de $|Q|$, já que nenhum bloco fica vazio; logo alguma rodada não separa ninguém. Nela, $P_{i+1} = P_i$, e a rodada seguinte calcularia as mesmas assinaturas sobre a mesma partição. Em `(a|b)*abb`, com 6 estados, as contagens 2, 3, 4, 5, 5 param na quarta rodada.
Uma máquina determinística de 6 estados e outra de 5, as duas lendo os mesmos símbolos e contado o de erro, concordam em todas as cadeias de até 9 símbolos. Por que concordam, então, em todas as cadeias?
**Resposta**
Ponha as linhas das duas numa tabela só, de 11 estados, e rode o refinamento, que não usa o estado inicial. A contagem começa em no máximo 2, cresce a cada rodada que separa e não passa de 11: no máximo $11 - 2 = 9$ rodadas separam. A rodada $r$ separa dois estados com uma testemunha de $r$ símbolos. Uma cadeia em que as máquinas discordam é testemunha dos dois estados iniciais. Sem nenhuma até 9 símbolos, nenhuma rodada separa os dois, e eles chegam ao ponto fixo no mesmo bloco: são equivalentes.
### Aplicar
Uma máquina não determinística sem transições vazias, sobre o alfabeto $\{a, b\}$, tem os estados 0, 1 e 2, inicial 0 e o 2 como único de aceitação. As transições são estas, e não há outras: do 0 ao 0, com `a` e com `b`; do 0 ao 1, com `a`; do 1 ao 2, com `a` e com `b`. Ela aceita as cadeias cujo penúltimo símbolo é `a`. Que conjuntos a construção de subconjuntos produz, quantos estados têm a determinizada e a reduzida, contado o de erro, e quantos tem a mínima?
**Resposta**
Os quatro conjuntos formados pelo 0 e por um subconjunto qualquer de $\{1, 2\}$: $\{0\}$, $\{0, 1\}$, $\{0, 2\}$ e $\{0, 1, 2\}$. Nenhum é vazio, e com o estado de erro a determinizada tem 5. As contagens do refinamento são 2, 4, 5, 5, e a reduzida também tem 5. Nenhuma seta leva ao erro, e a mínima tem 4, o piso $2^2$.
Para `-?[0-9]+`, sobre um alfabeto fechado de 11 símbolos, a determinizada tem 23 estados, e a reduzida, 4, as duas contando o de erro. Pela regra da soma dos estados menos 2, até que comprimento basta uma bateria de cadeias para que a concordância das duas máquinas valha para todas as cadeias sobre esse alfabeto, e quantas cadeias desse comprimento exato ela teria?
**Resposta**
Até o comprimento $23 + 4 - 2 = 25$. Cada um dos 25 lugares da cadeia recebe um dos 11 símbolos, e as cadeias de comprimento 25 são $11^{25}$, mais de $10^{26}$.
===== FIM DO MATERIAL =====