%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
S8((8<br/>inicial)) -->|ε| S0((0))
S8 -->|ε| S4((4))
S0 -->|a| S1((1))
S1 -->|ε| S2((2))
S2 -->|b| S3((3))
S4 -->|a| S5((5))
S5 -->|ε| S6((6))
S6 -->|c| S7((7))
S3 -->|ε| S9(((9<br/>aceitação)))
S7 -->|ε| S9
1 Determinização e minimização — Exercícios
Os três problemas a seguir falam de cadeias (fileiras de símbolos, como ab, que tem os símbolos a e b), de linguagens (conjuntos de cadeias), do alfabeto (a lista dos símbolos permitidos) e de máquinas que leem uma cadeia e a aceitam ou a recusam. O primeiro trata de trocar uma máquina de vários caminhos por uma de caminho único, de quais conjuntos de estados essa troca alcança, do que fazer quando essa troca chega ao conjunto vazio e de juntar os estados que se comportam igual. O segundo trata de quantos estados uma linguagem obriga a máquina a ter e de quanto custa montar a máquina de Thompson. O terceiro trata do alfabeto, que dá as colunas da tabela da máquina, e do que a escolha dele custa a quem digita o próprio nome num formulário. Trata também da comparação entre a máquina que sobra depois de juntar os estados que se comportam igual e a menor máquina possível, e do que uma lista de cadeias de teste confere, em contraste com o que os teoremas garantem. Nenhum pede programa escrito. Todos se resolvem com papel e lápis. Resolva na ordem: o primeiro faz as duas transformações numa máquina pequena, o segundo mede o que uma linguagem obriga a máquina a guardar, e o terceiro usa o que os dois primeiros praticam para decidir um caso.
1.1 Exercício 1: A tabela do padrão ab|ac
Nível Básico
Um programa precisa reconhecer só duas cadeias, ab e ac. Quem o escreveu descreveu as duas com o padrão ab|ac, um molde de texto em que a barra | escolhe um lado ou o outro. A construção de Thompson é o procedimento que transforma um padrão numa máquina. O desenho abaixo é a máquina que essa construção monta para esse padrão. Ela é não determinística: depois de ler um símbolo, pode estar em vários estados ao mesmo tempo. As setas marcadas com \varepsilon (épsilon) são transições vazias, que a máquina atravessa sem ler símbolo. O estado 8 é o inicial, e o 9 é o de aceitação.
Vamos transformar essa máquina numa determinística, em que de cada estado sai exatamente uma seta para cada símbolo, e depois juntar os estados da máquina nova que se comportam igual. O primeiro procedimento é a construção de subconjuntos: cada estado da máquina nova é um conjunto de estados do desenho. O primeiro conjunto contém o estado inicial e tudo o que se alcança dele só por transições vazias. Para levar um conjunto a outro com um símbolo, faça duas contas, nesta ordem: primeiro as transições que leem o símbolo, depois as transições vazias a partir dos destinos. Vamos chamar de catálogo a lista dos conjuntos que já receberam número, e de pendentes os conjuntos do catálogo cujas transições ainda falta calcular. O primeiro conjunto recebe o número 0 e entra no catálogo e nos pendentes. Todo conjunto novo recebe o próximo número ao entrar no catálogo e nos pendentes, e os símbolos são tomados na ordem a, b, c.
A conta pode dar o conjunto vazio, e há mais de um jeito de tratá-lo. Este exercício segue a escolha da construção do módulo: a transição vai para o estado de erro, o estado que recebe o símbolo que não serve, não aceita cadeia nenhuma e de onde a máquina não sai. O estado de erro recebe o último número e entra na contagem de estados. A máquina nova, com o estado de erro, é a máquina determinizada, e os estados de aceitação dela são os conjuntos que contêm o 9. A tabela de transição da determinizada tem uma linha por estado, inclusive o de erro, e uma coluna por símbolo, e cada cruzamento de uma linha com uma coluna é uma célula.
O segundo procedimento é a minimização, que junta os estados que se comportam igual. Dois estados são equivalentes quando nenhuma cadeia leva um deles à aceitação e o outro não, e quem descobre quais estados são equivalentes é o refinamento de partições. Uma partição divide os estados em grupos, chamados blocos, com cada estado em exatamente um bloco. A partição inicial separa os estados de aceitação dos demais. Cada rodada produz a partição seguinte, pondo no mesmo bloco os estados de mesma assinatura: a lista com o bloco do próprio estado e, para cada símbolo, o bloco do estado a que esse símbolo leva. O refinamento para na primeira rodada que devolve a partição que recebeu.
O que peço de você: três partes, nesta ordem. (a) Escreva o quadro da construção de subconjuntos: uma linha para cada conjunto tirado dos pendentes, com o conjunto tirado, os três conjuntos a que ele leva lendo a, lendo b e lendo c (escreva \emptyset onde a conta der o conjunto vazio) e os números dos conjuntos que entram no catálogo naquela linha. (b) Diga quantos estados tem a máquina determinizada, quantas das células da tabela dela apontam para o estado de erro, contando também as da linha do próprio erro, e explique a diferença entre o número de conjuntos do catálogo e os 2^{10} = 1024 subconjuntos que dez estados admitiriam. (c) Rode o refinamento de partições sobre a máquina determinizada: escreva a sequência de contagens de blocos, da partição inicial até a da primeira rodada que devolve a partição que recebeu. Diga quais estados terminam juntos num mesmo bloco, se algum terminar, e justifique, sem usar assinaturas, que os estados de um mesmo bloco são equivalentes.
Você terá terminado quando (a) trouxer uma linha por conjunto tirado dos pendentes, com os três conjuntos de destino e os números que entram no catálogo; (b) trouxer o número de estados, o número de células que apontam para o erro e a explicação da diferença para 1024; e (c) trouxer a sequência de contagens, a lista dos estados que terminam juntos num mesmo bloco, se houver, e a justificativa de que são equivalentes, escrita a partir da definição e sem assinaturas.
1.2 Exercício 2: O piso que o colega calculou
Nível Intermediário
Um colega quer saber quanto uma linguagem obriga a máquina determinística a guardar. Ele tomou a linguagem do módulo, a das cadeias em que o n-ésimo símbolo contado do fim é um a, e trocou o alfabeto: em vez de a e b, o alfabeto passou a ter três símbolos, a, b e c. Com n = 3, acc pertence à linguagem, porque o terceiro símbolo do fim é a, e bab não pertence.
O padrão dessa linguagem, o molde de texto que a descreve, é (a|b|c)*a(a|b|c)(a|b|c). A construção de Thompson, o procedimento que transforma um padrão numa máquina, trabalha sobre a árvore do padrão: um organograma de caixinhas, os nós, em que cada símbolo escrito é um nó de baixo, uma folha, e cada operação é um nó de cima. A alternância escolhe um de dois pedaços, como em a|b, a concatenação cola dois pedaços, como em ab, e o * repete um pedaço zero ou mais vezes. Cada a|b|c tem dois nós de alternância. A tabela de custos da construção de Thompson dá dois estados por folha, dois por alternância, dois pelo operador * e nenhum por concatenação, e com ela a máquina de Thompson desse padrão tem 34 estados. Um programa que segue o módulo mediu também a máquina determinizada, a que sai da construção de subconjuntos, e a reduzida, a que sai da minimização: 14 estados na determinizada e nove na reduzida. Nas medidas da determinizada e da reduzida, o estado de erro se conta como o módulo o conta. É o estado que recebe o símbolo que não serve e de onde a máquina não sai.
Um prefixo é um começo de cadeia, e uma continuação é o que se cola depois dele. Dois prefixos são distinguíveis quando alguma continuação, a testemunha, põe exatamente um deles na linguagem. Se há k prefixos distinguíveis dois a dois, toda máquina determinística da linguagem tem pelo menos k estados, e esse número k é o piso. Para saber o que a linguagem obriga, o colega calculou o piso e escreveu o raciocínio no diagrama, para os prefixos de comprimento 3. Ao ver a medida de 14 estados, concluiu que o programa tem defeito.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
A["Prefixos de comprimento 3<br/>sobre a, b e c: 27 cadeias"] --> B["Quaisquer duas cadeias diferentes<br/>diferem em alguma posição i,<br/>de 1 a 3, contada do começo"]
B --> C["Cola-se nas duas uma continuação<br/>de i − 1 símbolos: a posição i<br/>vira a terceira contada do fim"]
C --> D["Só uma das duas pertence à linguagem:<br/>as 27 cadeias são distinguíveis<br/>duas a duas"]
D --> E["Piso: 27 estados"]
E --> F["Medida do programa:<br/>14 estados na determinizada,<br/>menos que o piso"]
F --> G["Conclusão do colega:<br/>o programa tem defeito"]
O que peço de você: quatro partes, nesta ordem. (a) Diagnostique o raciocínio do colega seta por seta: para cada uma das seis setas do diagrama, diga se o passo que ela afirma vale para esta linguagem, e justifique; quando o passo só valer porque segue de uma seta anterior errada, diga isso e aponte a seta. (b) Determine o piso da linguagem para n = 3. Reparta as 27 cadeias de comprimento 3 em grupos de cadeias que nenhuma continuação separa. Para cada grupo com mais de uma cadeia, mostre isso analisando as continuações pelo comprimento delas. Justifique que cadeias de grupos diferentes são distinguíveis: dê a regra que produz a testemunha de cada par de grupos e, como exemplo, a testemunha concreta de um par. Escreva o piso que resulta. (c) Descreva uma máquina determinística em que todo estado tem uma transição para cada símbolo e que reconhece a linguagem para n = 3, com o menor número de estados que você conseguir justificar: o que cada estado guarda e como a leitura de um símbolo troca o estado. Diga por que esse número de estados basta, isto é, por que a máquina descrita aceita exatamente as cadeias da linguagem, e depois compare esse número com o piso de (b). Relacione a sua máquina com as duas medidas do programa: diga se cada uma, 14 e 9, contradiz o piso, e como cada uma se compara ao número de estados da sua máquina. (d) Escreva a fórmula do número de estados da máquina de Thompson para um n qualquer, sendo o padrão (a|b|c)*a seguido de n - 1 cópias de (a|b|c), e escreva o piso para um n qualquer. Monte a tabela dos dois para n de 1 a 8, diga a partir de que n o piso, sozinho, garante que toda máquina determinística da linguagem tem mais estados que a de Thompson, e diga o que o piso não afirma sobre os valores menores de n.
Você terá terminado quando (a) trouxer um veredito por seta, cada um com a razão; (b) trouxer a repartição das 27 cadeias em grupos, a análise das continuações para cada grupo com mais de uma cadeia, a regra que produz a testemunha de cada par de grupos, com uma testemunha concreta de exemplo, e o piso; (c) trouxer a descrição da máquina, com o que cada estado guarda e como a leitura de um símbolo troca o estado, a razão de esse número de estados bastar e a comparação dele com o piso, e, para cada uma das duas medidas, a comparação com o piso e com o número de estados da sua máquina; e (d) trouxer as duas fórmulas, a tabela de 1 a 8, o primeiro n em que o piso garante o que se pede e a frase sobre os valores menores de n.
1.3 Exercício 3: O campo de nome que recusou joão
Nível Desafiador
O site de matrícula de uma escola valida o campo “primeiro nome” com o padrão [a-z]+: uma ou mais letras minúsculas, de a a z, sem acento. A construção de Thompson, o procedimento que transforma um padrão numa máquina, trabalha sobre a árvore do padrão: um organograma de caixinhas, os nós, em que cada símbolo escrito é um nó de baixo, uma folha, e cada operação é um nó de cima. A faixa [a-z] vale por 26 símbolos e vira 26 folhas ligadas por 25 nós de alternância, que escolhem um de dois pedaços. E x+, para qualquer pedaço x do padrão, vira x seguido de x* (x repetido zero ou mais vezes), o que põe x duas vezes na árvore. A equipe compilou o padrão como o módulo ensina: a construção de Thompson monta a máquina de Thompson, a construção de subconjuntos a transforma na máquina determinizada, e a minimização produz a reduzida. O campo executa a reduzida.
Para conferir a compilação, a equipe rodou uma bateria de cadeias, uma lista de cadeias executada inteira de cada vez: todas as cadeias de letras de a a z, da vazia ao comprimento 3. As três máquinas deram a mesma resposta em todas. Semanas depois, a família de um aluno chamado João avisou que o campo recusa joão.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
P["Padrão<br/>[a-z]+"] --> T["Máquina<br/>de Thompson"]
T -->|"construção de subconjuntos"| D["Máquina<br/>determinizada"]
D -->|"minimização"| R["Máquina<br/>reduzida"]
T -.->|"bateria de cadeias"| D
D -.->|"bateria de cadeias"| R
E["Entrada do campo:<br/>joão"] --> R
R --> V["Resposta<br/>do campo: recusa"]
A equipe discute duas saídas: manter [a-z]+, ou trocá-lo por [a-zãçé]+, cuja faixa tem 29 símbolos. Conte ã, ç e é como um símbolo cada, do mesmo jeito que a ou z. Para as contas, a tabela de custos da construção de Thompson dá dois estados por folha, dois por alternância, dois pelo operador * e nenhum por concatenação, a operação que cola dois pedaços. O estado de erro se conta como o módulo o conta; é o que recebe o símbolo que não serve. A tabela de transição da máquina determinizada tem uma linha por estado e uma coluna por símbolo do alfabeto, e cada cruzamento de uma linha com uma coluna é uma célula.
A testemunha de dois estados é a cadeia que leva um deles à aceitação e o outro não, e dois estados de uma mesma máquina que não têm testemunha são equivalentes. A minimização junta os estados equivalentes em grupos, os blocos. A mínima de um padrão é a máquina de menor número de estados entre as determinísticas que reconhecem a linguagem dele.
O que peço de você: cinco partes, nesta ordem. (a) Diga se a recusa de joão contradiz o teorema da equivalência entre uma máquina não determinística e a determinizada dela, se a máquina de Thompson também recusa joão, e o que decidiu a recusa: o padrão, a construção de subconjuntos ou a minimização. Use a definição de alfabeto fechado. (b) Para cada um dos dois padrões, calcule o número de estados da máquina de Thompson, o de estados da máquina determinizada e o de células da tabela dela. (c) Para cada padrão, diga quantos estados tem a máquina reduzida e quantos tem a mínima, e justifique cada número: o da reduzida pela definição de estados equivalentes, com a testemunha que separa cada par de blocos, e o da mínima pela definição de mínima. Depois diga o que esses números mostram sobre o efeito de acrescentar os três símbolos no tamanho da máquina que a minimização devolve. (d) Para o padrão de 29 símbolos, considere a regra da soma dos estados menos 2: se duas máquinas determinísticas sobre o mesmo alfabeto concordam em todas as cadeias até um certo comprimento, elas concordam em todas as cadeias; esse comprimento é a soma dos números de estados das duas, contado o estado de erro de cada uma, menos 2. Calcule esse comprimento para a determinizada e a reduzida. Tome a bateria de cadeias desse padrão, montada sobre o alfabeto dele, de 29 símbolos, e calcule quantas cadeias ela reúne até o comprimento 3 e quantas cadeias só o comprimento 4 acrescenta. Diga o que sustenta a igualdade das duas máquinas e o que a bateria de cadeias confere nesse caso. (e) Escreva um parágrafo de decisão para a equipe com quatro elementos: qual padrão adotar; o custo de máquina dessa escolha, com os números de (b) e (c); o que ela custa a quem preenche o campo; e uma verificação a acrescentar à conferência da equipe. Escreva essa verificação como uma lista de cadeias com a resposta esperada de cada uma escrita à mão, como a bateria do módulo da construção de Thompson, e ponha joão nela. Essa lista difere da bateria de cadeias, que compara a resposta de uma máquina com a de outra e não traz resposta esperada.
Você terá terminado quando (a) trouxer uma resposta para cada uma das três perguntas, com a definição que a sustenta; (b) trouxer, para cada padrão, os três números com a conta que os produz; (c) trouxer, para cada padrão, os dois números, a testemunha de cada par de blocos da reduzida, a justificativa do número da mínima e a frase sobre o efeito no tamanho da máquina; (d) trouxer o comprimento, as duas contagens de cadeias, o que sustenta a igualdade e o que a bateria de cadeias confere; e (e) trouxer os quatro elementos, com o custo de máquina escrito pelos números de (b) e (c) e a verificação escrita como lista de cadeias com a resposta esperada de cada uma, joão entre elas.
Três hábitos valem para os três problemas. O primeiro: quando uma contagem puder ser feita pelo quadro passo a passo e pela conta por fórmula, faça pelos dois, e só siga quando os totais concordarem. O segundo: quando uma medida contraria a sua conta, confira as duas antes de decidir qual está errada. O terceiro: ao lado de cada afirmação de que duas máquinas são iguais, diga que cadeia a derrubaria, uma em que as duas respondessem diferente; ao lado de cada piso, escreva a testemunha de cada par de prefixos, ou a regra que a produz.