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

1.1 Objetivos e visão geral

Objetivos. Ao terminar este guia você deve ser capaz de: (i) transformar um AFN com transições vazias (\varepsilon) em um AFD pela construção de subconjuntos e provar que a linguagem não muda; (ii) explicar por que o número de estados pode explodir (2^{n}) e distinguir explosão da linguagem de defeito do programa; (iii) minimizar um AFD por refinamento de partições e justificar a parada; (iv) ler o código C++ da Peneira (determinizar, minimizar) e conferi-lo com uma bateria de cadeias.

Por que isso importa. O módulo 04 transforma uma expressão regular em um AFN (Thompson). Um AFN é cômodo de construir, mas é como palpitar em vários caminhos ao mesmo tempo; um analisador léxico precisa de uma máquina que, a cada caractere, consulte uma tabela e vá para um estado. A determinização troca os palpites simultâneos por um único estado que “lembra” o conjunto de palpites; a minimização depois junta estados que se comportam do mesmo modo. A Figura 1 mostra o percurso do padrão-exemplo do módulo.

Figura 1: Percurso do módulo com o padrão (a|b)*abb: 14 estados no AFN de Thompson, 6 no AFD (contando o estado de erro) e 5 na reduzida; a mínima tem 4 (a reduzida inclui o erro, que nenhuma seta alcança). Observe que a máquina encolhe em dois saltos, cada um com sua própria prova e sua própria conferência.

1.2 Fundamentos matemáticos necessários

Alfabeto, cadeia e linguagem. Um alfabeto \Sigma é um conjunto finito de símbolos; uma cadeia é uma sequência finita deles; \varepsilon é a cadeia sem símbolos; \Sigma^{*} é o conjunto de todas as cadeias sobre \Sigma (inclusive \varepsilon); uma linguagem é qualquer L \subseteq \Sigma^{*}. Uma expressão regular, como (a|b)*abb, é um padrão que descreve uma linguagem. Quantas cadeias há? Com k = |\Sigma| símbolos há k^{i} cadeias de comprimento i (k escolhas para cada uma das i posições). Até o comprimento L:

S = \sum_{i = 0}^{L}k^{i}\quad \Rightarrow \quad kS - S = k^{L + 1} - 1\quad \Rightarrow \quad S = \frac{k^{L + 1} - 1}{k - 1}

A segunda passagem vem de multiplicar S por k (cada parcela “desliza” uma posição) e subtrair S: só sobram k^{L + 1} e - k^{0} = - 1. Exemplo do módulo, k = 2, L = 6: S = \left( 2^{7} - 1 \right)/(2 - 1) = 127 cadeias. Essa conta dimensiona a bateria de testes de Seção 1.7.

Conjuntos, partições e equivalência. \mathcal{P}(Q) é o conjunto de todos os subconjuntos de Q: para cada elemento há duas escolhas (entra ou não), logo |\mathcal{P}(Q)| = 2^{|Q|}. Uma partição de Q é uma família de blocos não vazios, dois a dois disjuntos, cuja união é Q. Uma relação \sim é de equivalência se é reflexiva (p \sim p), simétrica (p \sim q \Rightarrow q \sim p) e transitiva (p \sim q e q \sim r \Rightarrow p \sim r); suas classes formam uma partição. Usaremos também indução: prova-se o caso base e, supondo o caso n (hipótese), prova-se o caso seguinte.

Autômatos. Um AFD é M = \left( Q,\Sigma,\delta,q_{0},F \right) com \delta:Q \times \Sigma \rightarrow Q total: de cada estado, com cada símbolo, sai exatamente uma seta; o que não tem destino útil vai ao estado de erro, de onde não se sai. A função estendida lê cadeias:

\hat{\delta}(q,\varepsilon) = q,\quad\quad\hat{\delta}(q,wa) = \delta\left( \hat{\delta}(q,w),a \right),\quad\quad L(M) = \{\, w \in \Sigma^{*} \mid \hat{\delta}\left( q_{0},w \right) \in F\,\}

Aqui q \in Q é um estado, w uma cadeia, a \in \Sigma um símbolo e F \subseteq Q os estados de aceitação. Um AFN pode ocupar vários estados ao mesmo tempo (o conjunto ativo), admite setas \varepsilon e não tem estado de erro.

1.3 O AFN de Thompson e seu tamanho

A expressão vira uma árvore com seis tipos de nó: três folhas (símbolo, \varepsilon, coringa .) e três operações (concatenação, alternância, fecho); +, ? e faixas como [0-9] são traduzidos antes. A construção de Thompson dá a cada nó uma regra, e o material tabela o custo em estados: 2 por folha, 2 por alternância, 2 por fecho e 0 por concatenação (ela só liga o fim de um bloco ao início do outro por uma seta \varepsilon). Logo

n_{AFN} = 2\,(f + a + s)

com f = folhas, a = alternâncias, s = fechos (números naturais contados na árvore). Cada um desses nós cria um estado novo de entrada e um de saída, de onde o fator 2. Para (a|b)*abb: folhas a,b,a,b,b (f = 5), uma alternância, um fecho, logo n_{AFN} = 2(5 + 1 + 1) = 14; para a(b|c)*d: 2(4 + 1 + 1) = 12; para a.c: 2(3 + 0 + 0) = 6. A Figura 2 mostra os 14 estados (numerados 0 a 13; início 6, aceitação 13).

Figura 2: AFN de Thompson de (a|b)*abb. Setas tracejadas são transições vazias (\varepsilon): não consomem símbolo. Observe o bloco (a|b)* (estados 6, 4, 0–3, 5, 7), que pode ser pulado ou repetido, seguido da cadeia fixa abb.

Simulação com abb. A cada símbolo calcula-se mover (quem lê o símbolo) e, em seguida, o fecho vazio E (definido em Seção 1.4):

lido	mover	conjunto ativo depois do fecho	tamanho
\varepsilon	—	{0,2,4,6,7,8}	6
a	{1,9}	{0,1,2,4,5,7,8,9,10}	9
b	{3,11}	{0,2,3,4,5,7,8,11,12}	9
b	{3,13}	{0,2,3,4,5,7,8,13}	8

O último conjunto contém o 13 (aceitação), logo abb é aceita; os tamanhos 6, 9, 9, 8 coincidem com o material. Esses conjuntos serão os estados do AFD.

1.4 Determinização: construção de subconjuntos

Duas operações. O fecho vazio E(S) é o menor conjunto que contém S e é fechado sob setas \varepsilon; mover(S,a) reúne os destinos das setas que leem a (ou o coringa) a partir de S:

E(S) = S \cup \{\, r \mid q \in E(S),\ q\overset{\varepsilon}{\rightarrow}r\,\},\quad\quad mover(S,a) = \{\, r \mid q \in S,\ q\overset{a}{\rightarrow}r\,\}

Definição do AFD D a partir do AFN N = \left( Q,\Sigma,\delta,q_{0},F \right):

q_{0}' = E\left( \{ q_{0}\} \right),\quad\quad\delta'(S,a) = E\left( mover(S,a) \right),\quad\quad F' = \{\, S \mid S \cap F \neq \varnothing\,\}

Os estados de D são subconjuntos de Q (portanto no máximo 2^{|Q|}), mas só os alcançáveis a partir de q_{0}' são criados. A ideia: depois de ler um prefixo, o estado de D é o conjunto de lugares onde N poderia estar.

Passo a passo em (a|b)*abb. O início é S_{0} = E\left( \{ 6\} \right) = \{ 0,2,4,6,7,8\}. Para cada subconjunto e cada símbolo:

estado	símbolo	mover	E(mover)	destino
S_{0}	a	{1,9}	{0,1,2,4,5,7,8,9,10}	S_{1} (novo)
S_{0}	b	{3}	{0,2,3,4,5,7,8}	S_{2} (novo)
S_{1}	a	{1,9}	S_{1}	S_{1}
S_{1}	b	{3,11}	{0,2,3,4,5,7,8,11,12}	S_{3} (novo)
S_{2}	a / b	{1,9} / {3}	S_{1} / S_{2}	S_{1} / S_{2}
S_{3}	a	{1,9}	S_{1}	S_{1}
S_{3}	b	{3,13}	{0,2,3,4,5,7,8,13}	S_{4} (novo; contém 13)
S_{4}	a / b	{1,9} / {3}	S_{1} / S_{2}	S_{1} / S_{2}

Só S_{4} contém o estado 13, logo F' = \{ S_{4}\}. A tabela do AFD, com o erro como sexto estado (todas as suas setas voltam a ele), é: S_{0}:(1,2), S_{1}:(1,3), S_{2}:(1,2), S_{3}:(1,4), S_{4}:(1,2), erro:(5,5) (colunas a, b). Conferência de contagem: 5 estados \times 2 símbolos = 10 destinos = 0 vazios + \, 4 novos + \, 6 repetidos; os “4 novos” são os cinco estados menos o inicial. O número bate com a contabilidade do código.

Figura 3: AFD de (a|b)*abb com cada estado rotulado pelo conjunto de estados de Thompson que ele representa (Figura 2). Cores iguais (S_{0} e S_{2}) anunciam estados que a minimização vai fundir (Seção 1.6); o duplo círculo (4) é o único de aceitação; o erro, tracejado, não recebe nenhuma seta de fora.

O algoritmo. Mantém-se um catálogo (subconjunto \rightarrow número) e uma lista de pendentes usada como pilha (último a entrar, primeiro a sair). Repete-se: tirar um pendente; para cada símbolo calcular E(mover); se o resultado é vazio, a transição fica sem destino (aponta para o erro); se é novo, recebe o próximo número e vira pendente; registrar o destino. Nesse exemplo os pendentes saem na ordem S_{0},S_{2},S_{1},S_{3},S_{4}, mas a numeração segue a ordem de descoberta.

Teorema da equivalência: L(D) = L(N). Prova por indução no comprimento de w. Afirmação: depois de ler w, o estado de D é exatamente o conjunto A(w) de estados em que N pode estar. Base: w = \varepsilon; D está em E\left( \{ q_{0}\} \right), e N pode estar em tudo que alcança por setas \varepsilon a partir de q_{0}. Passo: se D está em A(w), ao ler a vai a E\left( mover\left( A(w),a \right) \right), que são os lugares onde N pode estar depois de wa (lê-se a, depois passam-se quantas \varepsilon se queira). Por fim, D aceita w sse A(w) \cap F \neq \varnothing, sse algum caminho de N aceita w. \square

Cuidados de implementação. (a) A chave do catálogo deve ser o conjunto ordenado e sem repetição; senão o mesmo conjunto receberia números diferentes conforme a ordem de chegada. (b) O conjunto vazio não vira estado. (c) O alfabeto é fechado: são os símbolos concretos que aparecem nas setas, e o coringa vale por cada um deles sem ocupar coluna própria. (d) Erros típicos de cópia: esquecer o E inicial, inverter a ordem (mover antes de E) e não aplicar o coringa a todos os símbolos.

1.5 Explosão de estados

Para a família “o n-ésimo símbolo contado do fim é a” ((a|b)*a seguido de n - 1 cópias de (a|b)), o material mede e dá as fórmulas:

n	1	2	3	4	5	6	7	8	fórmula
Thompson	10	16	22	28	34	40	46	52	6n + 4
determinizada	4	6	10	18	34	66	130	258	2^{n} + 2
reduzida	3	5	9	17	33	65	129	257	2^{n} + 1

Origem da primeira fórmula: com n = 1 há 3 folhas, 1 alternância e 1 fecho: 2(3 + 1 + 1) = 10; cada cópia extra de (a|b) soma 2 folhas e 1 alternância, ou seja, 2 \cdot 3 = 6 estados; logo 10 + 6(n - 1) = 6n + 4. Substituição: n = 5 dá 6 \cdot 5 + 4 = 34 e 2^{5} + 2 = 34; n = 8 dá 52 e 2^{8} + 2 = 258. Interpretação: o AFN cresce linearmente, o AFD exponencialmente, e as curvas se cruzam em n = 5 (Figura 4, parte b).

Por que 2^{n} é inevitável (piso). Duas cadeias u \neq v de comprimento n diferem em alguma posição i. Acrescente a ambas uma cauda de i - 1 símbolos: o n-ésimo símbolo do fim passa a ser u_{i} numa e v_{i} na outra, uma aceita e a outra rejeita. Há 2^{n} cadeias de comprimento n, todas duas a duas separáveis; um AFD com menos de 2^{n} estados poria duas delas no mesmo estado (princípio da casa dos pombos) e não poderia separá-las. Logo qualquer AFD precisa de \geq 2^{n} estados; o medido, 2^{n} + 1, só acrescenta o erro.

Figura 4: (a) AFD mínimo de L_{2} (n = 2): os estados lembram os dois últimos símbolos; aceita-se quando o penúltimo é a (duplo círculo). (b) Contagem de estados para n = 1,\ldots,8: a reta cinza (Thompson) é cruzada pelas curvas exponenciais em n = 5 (34 = 34); a tracejada é o piso 2^{n}.

Diagnóstico. Se a reduzida fica próxima da determinizada, o crescimento vem da linguagem. Se fica várias vezes menor, desconfie do programa (chave sem ordenação, coringa expandido em folhas).

1.6 Minimização por refinamento de partições

Estados equivalentes. p \equiv q quando nenhuma cadeia os separa quanto à aceitação:

p \equiv q \Leftrightarrow \forall w \in \Sigma^{*}:\ \hat{\delta}(p,w) \in F \Leftrightarrow \hat{\delta}(q,w) \in F

(lê-se: para toda cadeia w, os dois terminam em aceitação ou os dois não). É uma relação de equivalência, logo suas classes particionam Q.

Algoritmo. Partição inicial: \{ F,\ Q \setminus F\} (a cadeia vazia separa os dois blocos). A cada rodada, a assinatura de um estado q é o seu bloco atual \beta(q) mais os blocos de seus destinos:

sig(q) = \left( \beta(q),\ \beta\left( \delta\left( q,a_{1} \right) \right),\ \ldots,\ \beta\left( \delta\left( q,a_{k} \right) \right) \right)

Estados com a mesma assinatura ficam juntos; para quando a rodada não muda a partição (ponto fixo). Em (a|b)*abb (estados 0..4 = S_{0}..S_{4} e 5 = erro; Figura 5):

• Inicial: F = \{ 4\} e N = \{ 0,1,2,3,5\}: dois blocos.
• Rodada 1: só o 3 tem assinatura diferente (com b vai a F): sig(3) = (N,N,F) contra (N,N,N) dos demais. Três blocos; testemunha b.
• Rodada 2: o 1 vai com b ao bloco \{ 3\}, enquanto 0, 2 e erro vão a N': separa-se o 1 (quatro blocos; testemunha bb).
• Rodada 3: o erro, com a, volta a si mesmo, enquanto 0 e 2 vão ao bloco \{ 1\}: separa-se o erro (cinco blocos; testemunha abb).
• Rodada 4: nada muda: ponto fixo. Contagens 2,3,4,5,5 e blocos finais \{ 0,2\},\{\text{erro}\},\{ 1\},\{ 3\},\{ 4\}.

Figura 5: Evolução da partição de (a|b)*abb. Contornos azuis são blocos; cores são as classes finais. Observe que a “testemunha” de cada separação é a cadeia que um estado aceita e o outro não; 0 e 2 nunca se separam: são equivalentes.

Teorema de correção. As partições só se refinam (blocos nunca se juntam) e o número de blocos não passa de |Q|; logo o processo termina. No ponto fixo, dois estados estão no mesmo bloco se e somente se são equivalentes: se foram separados, uma testemunha existe (a cadeia que acompanha a separação); se não foram, nenhuma assinatura os distingue, e por indução no comprimento de w nenhuma w os separa. Por que não parar antes: parar quando a contagem chega a um número esperado só dá certo se esse número for o do ponto fixo, e ele só se conhece rodando o refinamento até o fim. Em (a|b)*abb, parar com dois ou três blocos deixa o estado inicial no bloco do erro, e a máquina não aceita cadeia nenhuma: erra em 255 das 2^{11} - 1 = 2047 cadeias de comprimento \leq 10 (a soma de Seção 1.2 com k = 2, L = 10). Parar com quatro blocos dá, por acaso, a linguagem certa, com o estado inicial fazendo também o papel do erro; nenhum teste com cadeias acusa essa parada, e é por isso que o ponto fixo é a única regra segura.

Máquina reduzida e máquina mínima. A reduzida tem um estado por bloco: b_{0} = \{ 0,2\}, b_{1} = \{ 1\}, b_{2} = \{ 3\}, b_{3} = \{ 4\} (aceitação) e o erro; tabela b_{0}:(1,0), b_{1}:(1,2), b_{2}:(1,3), b_{3}:(1,0), erro:\left( \text{erro},\text{erro} \right). A mínima só conta os estados alcançáveis: aqui o erro é inalcançável, então são 4 (Figura 6).

Figura 6: AFD reduzido de (a|b)*abb: cada estado é um bloco da Figura 5 (mesmas cores). Compare com a Figura 3: o 0 e o 2 foram fundidos em b_{0}, e o erro ficou isolado.

Teorema da unicidade. O autômato mínimo tem o menor número de estados possível e é único a menos de renomeação dos estados. Consequência: duas expressões regulares são equivalentes se, após converter, determinizar e minimizar, as máquinas coincidem.

padrão	Thompson	determinizada	reduzida	mínima
(a|b)*abb	14	6	5	4
a(b|c)*d	12	6	4	4
-?[0-9]+	84	23	4	4
a.c	6	5	5	5

1.7 Verificação: bateria de cadeias e dois saltos

A bateria compara as respostas de duas máquinas sobre todas as cadeias até um comprimento. Só vira prova se o comprimento chegar à soma dos estados das duas máquinas determinísticas, contado o de erro, menos 2; nos comprimentos abaixo, que são os usados aqui, não prova, mas apanha erros de cópia. Quantidade: \frac{k^{L + 1} - 1}{k - 1}, isto é, 127 (k = 2,L = 6), 1365 (k = 4,L = 5 para a(b|c)*d) e 31 (k = 2,L = 4 para a.c). Confere-se Thompson contra determinizada e determinizada contra reduzida, separadamente: comparar só as pontas pode deixar passar dois erros que se cancelam. Ordem de investigação: (1) a sequência de contagens; (2) o salto em que a discordância surge; (3) os suspeitos daquela etapa. Nos três padrões, as três máquinas concordam em toda a bateria.

1.8 Análise do código da Peneira

Objetivo e arquivos. 05_determinizacao.h/.cpp implementam o módulo: entrada, um Afn (e o alfabeto); saída, um Afd e um resultado com o número de estados.

• alfabetoDoAfn: coleta os símbolos distintos do AFN, ignorando \varepsilon e o coringa, em ordem; é o alfabeto fechado.
• avancar: dado um conjunto, segue as setas que casam com o símbolo ou com o coringa, aplica o fecho vazio, ordena e remove repetidos; isto é E(mover) e garante a chave canônica.
• determinizar: usa std::map<std::vector<Estado>, Estado> (catálogo) e um vetor pendentes como pilha (back/pop_back). Monta a tabela destinos antes do Afd, pois o construtor precisa do número de estados; kSemDestino é (Estado)-1, valor distinto do estado 0, e marca “vai ao erro”. Estado aceita se o subconjunto contém a aceitação do AFN; o nome do estado é o conjunto entre chaves.
• minimizar: a partição inicial separa aceitantes de não aceitantes; cada rodada calcula a assinatura de cada estado e a guarda em um std::map de vetores; para quando o número de blocos não muda; blocosPorRodada registra as contagens (ex.: 2,3,4,5,5). Na reconstrução o bloco do erro vai para o último índice e os demais viram b0, b1, …
• todasAsCadeias e compararSobre (duas sobrecargas: Afd\timesAfd e Afn\timesAfd) geram a bateria e param na primeira Discordancia (houve, cadeia, primeiraAceitou, segundaAceitou), que distingue “nenhuma discordância” de “discordância na cadeia vazia”.

Decisões de projeto. std::map com chave vetor ordenado dá o catálogo sem escrever uma função de hash; a pilha torna o laço simples; a assinatura em map agrupa estados sem comparar pares; kSemDestino separa “sem destino” de “destino 0”. Limitações: o código depende de o construtor do Afd criar o erro e apontar para ele as setas sem destino; todasAsCadeias cresce exponencialmente com |\Sigma| (com 11 símbolos, como em -?[0-9]+, só comprimentos curtos são viáveis).

1.9 Casos especiais e cuidados

• Teto 2^{|Q|} é só teto: o AFN de (a|b)*abb permitiria até 2^{14} = 16384 subconjuntos e apenas cinco são alcançáveis; no de 84 estados o teto seria 2^{84} \approx 1,9 \times 10^{25}, e foram gerados 23 (contando o erro).
• Coringa e alfabeto fechado. Em a.c o alfabeto é \{ a,c\} (o b não aparece em nenhuma seta). A simulação da máquina de Thompson não usa alfabeto: nela, a seta do coringa serve a qualquer caractere, e ela aceita abc. A determinizada não tem coluna para b e recusa abc. As duas concordam em todas as cadeias sobre \{ a,c\}, que é o que o teorema garante; fora do alfabeto fechado, a garantia não vale. Por isso o coringa se lê como “qualquer símbolo de \Sigma”.
• Terminologia que pede cuidado: “mínima” vs “reduzida” (a reduzida pode incluir o erro inalcançável: em (a|b)*abb ela tem cinco estados e a mínima, sem o erro, quatro); “bloco” (de partição e, na reconstrução, estado b0..); “equivalente” (estados vs expressões).

1.10 Síntese

ideia	fórmula / regra	onde falha se esquecida
tamanho de Thompson	n_{AFN} = 2(f + a + s)	contagem errada de estados
determinização	\delta'(S,a) = E\left( mover(S,a) \right)	esquecer E inicial; ordem trocada
equivalência L(D) = L(N)	indução: estado de D = conjunto ativo de N	confiar sem bateria
explosão	piso 2^{n} (casa dos pombos)	confundir linguagem com defeito
minimização	sig(q) até o ponto fixo	parar por contagem
verificação	\frac{k^{L + 1} - 1}{k - 1} cadeias, dois saltos	erros que se cancelam

1.11 Exercícios de fixação

1. (Conceitual) Por que o conjunto vazio não vira estado do AFD? E por que o catálogo exige subconjuntos ordenados?
2. (Cálculo) Use n_{AFN} = 2(f + a + s) para a*b. Desenhe o AFN de Thompson e dê o conjunto E\left( \{ q_{0}\} \right).
3. (Determinização) Determinize a*b (Thompson: estados 0 e 1 para a, 2 início do fecho, 3 saída do fecho, 4 e 5 para b). Dê os subconjuntos, a tabela e as contagens de minimização.
4. (Combinado) Para ab|ac, o AFN de Thompson tem 10 estados e os subconjuntos são {0,4,8}, {1,2,5,6}, {3,9}, {7,9}. Dê as contagens e quantas células da tabela (alfabeto {a,b,c}) apontam para o erro.
5. (Minimização) AFD de 6 estados, colunas a,b: 0:(1,3), 1:(4,2), 2:(1,3), 3:(4,0), 4:(1,5), 5:(4,0); aceitação \{ 2,5\}. Minimize e descreva a linguagem.
6. (Matemático) Quantas cadeias tem a bateria sobre três símbolos até comprimento 4? E para que n a curva exponencial 2^{n} + 2 passa a Thompson 6n + 4?
7. (Interpretação) Uma versão do programa produz para (a|b)*abb as contagens 2,3 e parou. O que aconteceu e como detectar?

1.12 Gabarito comentado

1. O vazio significa “nenhum palpite vivo”: é o erro, que o Afd já cria; um estado a mais duplicaria o erro. Com chaves desordenadas, {1,9} e {9,1} seriam estados distintos para o mesmo conjunto.
2. a*b: folha a, folha b, fecho s = 1: 2(2 + 0 + 1) = 6 estados. E\left( \{ 2\} \right) = \{ 0,2,3,4\} (o início 2 vai por \varepsilon a 0 e a 3; 3 vai a 4).
3. S_{0} = \{ 0,2,3,4\}; a: mover = \{ 1\}, E = \{ 0,1,3,4\} = S_{1}; b: mover = \{ 5\} = S_{2}. S_{1}: a\rightarrow S_{1}, b\rightarrow S_{2}. S_{2}: sem setas, vai ao erro. Com o erro, quatro estados; tabela S_{0}:(1,2), S_{1}:(1,2), S_{2}:(3,3), erro:(3,3); aceitação \{ S_{2}\}. Contagens 2,3,3: S_{0} \equiv S_{1}; reduzida 3, mínima 3 (o erro é alcançável por S_{2}).
4. Cinco estados com o erro; contagens 2,3,4,4 (\{ 3,9\} e \{ 7,9\} são aceitantes sem setas, logo equivalentes): reduzida 4, mínima 4. Células: 5 \times 3 = 15, só 3 não vão ao erro (S_{0} com a; S_{1} com b e c), logo 12.
5. Blocos \{ 0,3\},\{ 1,4\},\{ 2,5\}, contagens 2,3,3; três estados. A linguagem é “termina em ab”: o estado do bloco \{ 2,5\} só se alcança lendo b logo depois de um a.
6. \left( 3^{5} - 1 \right)/(3 - 1) = 121. 6n + 4 = 2^{n} + 2 em n = 5 (34 = 34); para n \geq 6 a exponencial passa.
7. Parou antes do ponto fixo (o correto é 2,3,4,5,5): o estado inicial ficou no bloco do erro, e a máquina não aceita cadeia nenhuma. Detecta-se pela bateria no salto determinizada \rightarrow reduzida.

Fonte: o material deste módulo, Determinização e minimização.