1 Autômatos finitos determinísticos — 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, num papel em branco, tudo o que você lembra sobre autômatos finitos determinísticos: definições, propriedades, exemplos e contas. Só então abra a folha abaixo e marque o que ficou de fora e o que você escreveu diferente.
- Um autômato finito determinístico é a quíntupla M = (Q, \Sigma, \delta, q_0, F): Q finito e não vazio, \Sigma alfabeto finito, \delta : Q \times \Sigma \to Q, q_0 \in Q e F \subseteq Q.
- A função de transição é total: cada par de estado e símbolo tem um destino. F = \emptyset e F = Q são legítimos.
- O desenho com setas faltando abrevia uma máquina completa: o completamento acrescenta q_e, manda a ele toda transição omitida, inclusive as de q_e, e preserva a linguagem.
- Um estado é absorvente quando volta a si por todo símbolo. Fora de F, é estado de erro, e sem a absorção o completamento mudaria a linguagem; em F, é de aceitação irreversível.
- Uma configuração é o par do estado corrente com o sufixo ainda não consumido, e a inicial sobre w é (q_0, w); o já lido fica fora dela.
- Cada passo consome um símbolo, e toda configuração com sufixo não vazio tem exatamente uma seguinte: n símbolos se leem em n passos, sem retrocesso.
- A função estendida tem caso base \hat{\delta}(q, \varepsilon) = q e passo \hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a).
- L(M) = \{ w \in \Sigma^* : \hat{\delta}(q_0, w) \in F \}: decide só o estado alcançado depois da cadeia inteira, e por isso \varepsilon \in L(M) se e somente se q_0 \in F. Regular é a linguagem que algum autômato finito determinístico reconhece.
- A máquina recusa de três formas: lendo símbolo do alfabeto cuja transição leva ao erro, lendo símbolo fora do alfabeto, ou consumindo a cadeia inteira e parando fora de F.
- Se \hat{\delta}(q_0, u) = \hat{\delta}(q_0, v), então uz e vz recebem a mesma resposta para todo z: o estado resume os passados que a máquina deixou de distinguir.
- Cada “opcional, mas, se presente, obrigatório” da especificação pede um estado intermediário fora de F.
- Os prefixos u e v são distinguíveis quando alguma testemunha z põe exatamente uma de uz e vz em L; z pode ser \varepsilon, e u e v são cadeias quaisquer de \Sigma^*.
- Com k prefixos dois a dois distinguíveis, todo autômato que reconhece L tem pelo menos k estados. O piso não garante a sua máquina: que ela reconhece L se prova nela, por indução sobre o prefixo, com uma descrição para cada estado.
- A distinguibilidade não é transitiva: u separado de v, e v de w, não diz nada sobre u e w.
- Quando os prefixos dois a dois distinguíveis formam família infinita, como
(,((,(((nos parênteses balanceados, nenhum autômato finito determinístico reconhece a linguagem. - Na matriz densa, a tabela tem B(n,k,b) = n \cdot k \cdot b bytes para n estados, o de erro incluído, k símbolos e b bytes por célula. Mapear byte em coluna troca as 256 colunas pelo alfabeto declarado, mais o vetor de colunas, de 256 entradas por autômato.
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 determinístico
- Função de transição
- Tabela de transição
- Estado de erro
- Estado absorvente
- Configuração
- Passo de computação
- Função de transição estendida
- Linguagem reconhecida
- Linguagem regular
- Prefixos distinguíveis
- Testemunha
- Limite inferior de estados
| De | Relação | Para |
|---|---|---|
| Autômato finito determinístico | tem como componente | Função de transição |
| Função de transição | é armazenada na | Tabela de transição |
| Estado de erro | torna total a | Função de transição |
| Estado de erro | é um caso de | Estado absorvente |
| Tabela de transição | reserva uma linha ao | Estado de erro |
| Passo de computação | é uma relação entre | Configuração |
| Passo de computação | consulta a | Função de transição |
| Função de transição estendida | estende às cadeias a | Função de transição |
| Função de transição estendida | resume zero ou mais | Passo de computação |
| Linguagem reconhecida | é definida pela | Função de transição estendida |
| Linguagem regular | é reconhecida por | Autômato finito determinístico |
| Testemunha | separa dois | Prefixos distinguíveis |
| Limite inferior de estados | se demonstra com | Prefixos distinguíveis |
| Limite inferior de estados | vale para todo | Autômato finito determinístico |
1.3 Não confunda
Estado de erro e estado absorvente: todo estado absorvente é um estado de erro?
Absorvente é o estado que volta a si por todo símbolo do alfabeto. O estado de erro é o absorvente que fica fora de F; o absorvente que pertence a F é um estado de aceitação irreversível. A máquina de um único estado q, com F = Q = \{q\}, reconhece \Sigma^*: q é absorvente, porque toda transição volta a ele, e pertence a F, logo é absorvente sem ser estado de erro.
Recusa e queda no estado de erro: uma cadeia recusada passa necessariamente pelo estado de erro?
A recusa se decide pelo estado alcançado depois da cadeia inteira, fora de F. Cair no erro é uma das maneiras de terminar ali, e a outra é consumir a cadeia sem tocá-lo. Na máquina de identificadores, cujo estado inicial não aceita, a cadeia vazia é recusada com zero passos. Na de números com sinal, + leva o peão de inicio a sinal, e ele para ali, sem passar pelo erro.
Configuração e prefixo já lido: duas execuções que leram prefixos diferentes podem estar na mesma configuração?
Podem, porque a configuração é o par do estado corrente com o sufixo ainda não consumido, e o prefixo lido não entra nele. Na máquina de números com sinal, a execução sobre 4.5 chega, depois de um passo, a (inteiro, .5); a execução sobre 45.5 chega à mesma configuração depois de dois. Os prefixos lidos, 4 e 45, diferem, e dali em diante as duas execuções coincidem até a resposta, aceita.
Limite inferior de estados e suficiência dos estados: exibir três prefixos dois a dois distinguíveis e uma máquina de três estados demonstra que a máquina reconhece a linguagem?
Demonstra só o piso: toda máquina para a linguagem precisa de ao menos três estados. Que a sua a reconhece se prova sobre ela, por indução sobre o prefixo, com uma descrição para cada estado. Nos identificadores (letra minúscula seguida de letras, dígitos ou sublinhado), \varepsilon, a e 1 se separam dois a dois: \varepsilon separa a dos outros dois, e a separa \varepsilon de 1, porque a é identificador e 1a não é. Uma máquina de três estados, contando o de erro, que levasse o dígito inicial de inicio a corpo respeitaria o piso e aceitaria 1.
1.4 Perguntas em três níveis
1.4.1 Lembrar
O que é uma configuração de M, e como se define a relação de passo entre configurações?
Uma configuração de M sobre uma cadeia é um par (q, w) \in Q \times \Sigma^*. Nele, q é o estado corrente e w é o sufixo da entrada ainda não consumido. A configuração inicial da máquina sobre a cadeia w é (q_0, w).
A relação de passo \vdash_M entre configurações é definida por (q, aw) \vdash_M (\delta(q,a), w) para todo q \in Q, a \in \Sigma e w \in \Sigma^*.
Como se define a linguagem reconhecida por M, e quando uma linguagem é regular?
A linguagem reconhecida por M é L(M) = \{ w \in \Sigma^* : \hat{\delta}(q_0, w) \in F \}. Uma linguagem L é dita regular quando existe um autômato finito determinístico M tal que L = L(M).
O que torna dois prefixos distinguíveis, e que piso de estados eles impõem?
Dois prefixos u, v \in \Sigma^* são distinguíveis com respeito a uma linguagem L quando existe uma cadeia z \in \Sigma^* com a propriedade a seguir. Exatamente uma das cadeias uz e vz pertence a L. Tal cadeia z chama-se testemunha da distinção.
Se existem k prefixos dois a dois distinguíveis com respeito a L, então todo autômato finito determinístico que reconhece L tem pelo menos k estados.
1.4.2 Explicar
Por que o estado de erro acrescentado no completamento precisa ser absorvente?
Suponha que, de q_e, algum símbolo levasse a um estado útil. Então uma cadeia que tinha caído no erro poderia sair dele e terminar em F: a máquina completa aceitaria o que a parcial recusava, e o completamento deixaria de ser abreviação para virar alteração. Na máquina de identificadores, se q_e fosse a corpo pela letra a, a cadeia 1a seria aceita, porque 1 leva ao erro e o a traria o peão de volta a corpo.
Por que a leitura de uma cadeia de comprimento n termina em exatamente n passos, sem nunca voltar atrás?
Cada passo consome exatamente um símbolo do sufixo, e enquanto houver símbolo existe exatamente uma configuração seguinte, porque \delta é total e devolve um único estado. Sem escolha, não há caminho alternativo a tentar nem por onde voltar. O sufixo se esvazia depois de n passos, qualquer que seja a cadeia, e cada passo é uma consulta a \delta e uma atribuição: com consulta em tempo constante, o custo é linear em n.
Se dois prefixos levam a máquina ao mesmo estado, por que nenhuma continuação os separa depois?
Ler uz é ler u e, do estado alcançado, ler z: \hat{\delta}(q_0, uz) = \hat{\delta}(\hat{\delta}(q_0, u), z), por indução sobre z na definição de \hat{\delta}. Se \hat{\delta}(q_0, u) = \hat{\delta}(q_0, v) = p, as duas leituras continuam de p e terminam no mesmo estado \hat{\delta}(p, z), que está ou não está em F para as duas ao mesmo tempo. Na máquina de números com sinal, +3 e 27 chegam a inteiro, e daí em diante nenhuma continuação separa as duas: com .5 as duas são aceitas, com . as duas são recusadas.
1.4.3 Aplicar
A máquina de números com sinal tem alfabeto de 13 símbolos (os dez dígitos, +, - e .) e reconhece sinal opcional, parte inteira e parte fracionária opcional: a parte inteira tem um ou mais dígitos, e a fracionária, quando existe, é um ponto e um ou mais dígitos. Para cada cadeia, -0.5, 5-, + e 1e5, diga se ela é aceita e, se for recusada, por qual das três formas, com a posição contada a partir de zero.
-0.5 é aceita: inicio, sinal, inteiro, apos_ponto, fracao. 5- cai no erro na posição 1, por símbolo do alfabeto: de inteiro, o - leva ao erro. + consome a cadeia inteira e para em sinal, fora de F, sem passar pelo erro. 1e5 cai no erro na posição 1, por símbolo fora do alfabeto, e os passos seguintes ficam no erro.
Sobre o alfabeto \{a, b\}, a linguagem reúne toda cadeia em que ab aparece como subcadeia. Contando todos os estados, quantos tem a menor máquina que a reconhece, e por que nenhuma tem menos?
Três. Os prefixos \varepsilon, a e ab se separam dois a dois. A testemunha vazia separa ab de cada um dos outros dois, e uma testemunha que separa \varepsilon de a é b, porque ab pertence à linguagem e b não. Pelo limite inferior, nenhuma máquina tem menos de três estados.
Três bastam: s_0, nenhum ab e a cadeia não termina em a; s_1, nenhum ab e termina em a; s_2, já contém ab, único em F. Pelo a, s_0 e s_1 vão a s_1; pelo b, s_0 fica em s_0 e s_1 vai a s_2; s_2 volta a si pelos dois.
A máquina de identificadores tem dois estados úteis e alfabeto declarado de 37 símbolos: as 26 letras minúsculas, os dez dígitos e o sublinhado. Pela fórmula B(n,k,b), quantos bytes ocupa a tabela se cada destino ocupar 2 bytes, e quantos ocuparia com uma coluna para cada um dos 256 valores de um byte?
Com o estado de erro, n = 3. A tabela ocupa 3 \cdot 37 \cdot 2 = 222 bytes, e indexada pelo byte ocuparia 3 \cdot 256 \cdot 2 = 1.536 bytes, cerca de sete vezes mais, qualquer que seja b. A comparação é só de tabela: o mapeamento de byte para coluna acrescenta o vetor de colunas, de 256 entradas por autômato, que a fórmula não conta.
1.5 Cartões
Leia a frente, diga ou escreva a definição de memória e só então abra o cartão.
Um autômato finito determinístico é uma quíntupla M = (Q, \Sigma, \delta, q_0, F). Nela, Q é um conjunto finito e não vazio de estados e \Sigma é um alfabeto finito. A função de transição é \delta : Q \times \Sigma \to Q. O estado inicial é q_0 \in Q, e F \subseteq Q é o conjunto de estados de aceitação.
Para todo autômato com função de transição parcial \delta' : Q \times \Sigma \rightharpoonup Q existe um autômato com função de transição total que reconhece exatamente a mesma linguagem. Constrói-se M = (Q \cup \{q_e\}, \Sigma, \delta, q_0, F), com q_e \notin Q. Define-se \delta(q, a) = \delta'(q, a) onde \delta' estiver definida. Nos demais casos, \delta(q, a) = q_e, inclusive para todo par (q_e, a).
Um estado q \in Q é absorvente quando \delta(q, a) = q para todo a \in \Sigma. Um estado absorvente que não pertence a F chama-se estado de erro ou sumidouro; um estado absorvente que pertence a F é um estado de aceitação irreversível.
Uma configuração de M sobre uma cadeia é um par (q, w) \in Q \times \Sigma^*. Nele, q é o estado corrente e w é o sufixo da entrada ainda não consumido. A configuração inicial da máquina sobre a cadeia w é (q_0, w).
A relação de passo \vdash_M entre configurações é definida por (q, aw) \vdash_M (\delta(q,a), w) para todo q \in Q, a \in \Sigma e w \in \Sigma^*. Denota-se por \vdash_M^{*} o fecho reflexivo e transitivo de \vdash_M, isto é, a relação que vale entre duas configurações ligadas por zero ou mais passos.
A função \hat{\delta} : Q \times \Sigma^* \to Q é definida por indução sobre a cadeia. O caso base é \hat{\delta}(q, \varepsilon) = q. O passo é \hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a), para todo w \in \Sigma^* e a \in \Sigma. Vale \hat{\delta}(q,w) = p se e somente se (q, w) \vdash_M^{*} (p, \varepsilon).
A linguagem reconhecida por M é L(M) = \{ w \in \Sigma^* : \hat{\delta}(q_0, w) \in F \}. Uma linguagem L é dita regular quando existe um autômato finito determinístico M tal que L = L(M).
Dois prefixos u, v \in \Sigma^* são distinguíveis com respeito a uma linguagem L quando existe uma cadeia z \in \Sigma^* com a propriedade a seguir. Exatamente uma das cadeias uz e vz pertence a L. Tal cadeia z chama-se testemunha da distinção.
Se existem k prefixos dois a dois distinguíveis com respeito a L, então todo autômato finito determinístico que reconhece L tem pelo menos k estados.
Regra que, dado o estado corrente e o símbolo lido, determina para onde a máquina vai. Sua versão estendida faz o mesmo para uma cadeia inteira, aplicando a regra símbolo a símbolo.
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 "Autômatos finitos determinísticos", módulo 03 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
# Autômatos finitos determinísticos — Guia
Uma máquina que reconhece números com sinal recebe três cadeias, fileiras de símbolos: `-240.75`, `42.` e `++5`. Entre um símbolo e o seguinte, ela guarda só o estado, a situação em que está. Ela aceita a primeira e recusa as outras duas. Em `++5`, o segundo símbolo a leva ao estado de erro. Dali ela não sai. Em `42.`, ela lê os três símbolos sem passar pelo erro, e recusa mesmo assim.
A regra da máquina, chamada **especificação**, cabe numa linha: sinal opcional, ao menos um dígito, parte fracionária opcional, que é um ponto com ao menos um dígito depois. Dela saem cinco estados úteis, fora o de erro, e dois deles são fáceis de esquecer. Executar a máquina pronta é trabalho mecânico: uma consulta a uma tabela por símbolo, só com o estado atual e o símbolo lido. Projetá-la é escrevê-la a partir da regra, e exige decidir o que do passado ainda fará diferença.
## Três ideias que sustentam a máquina
**Definição — Autômato finito determinístico**
Um autômato finito determinístico é uma quíntupla $M = (Q, \Sigma, \delta, q_0, F)$. Nela, $Q$ é um conjunto finito e não vazio de estados e $\Sigma$ é um alfabeto finito. A função de transição é $\delta : Q \times \Sigma \to Q$. O estado inicial é $q_0 \in Q$, e $F \subseteq Q$ é o conjunto de estados de aceitação.
A definição chama a máquina pelo nome formal. **Quíntupla** é uma lista de cinco coisas, e o alfabeto, a dos símbolos permitidos. A primeira ideia está em $\delta : Q \times \Sigma \to Q$: lê-se "delta recebe um estado e um símbolo e devolve um estado". A função é total: cada par tem destino. O que o desenho deixa sem seta vai para o erro. A cadeia é aceita quando o estado alcançado depois do último símbolo está em $F$.
A segunda ideia diz o que um estado significa. Se dois prefixos, pedaços iniciais de cadeia, chegam ao mesmo estado, qualquer continuação leva os dois ao mesmo estado e à mesma resposta. Cada estado nomeia um grupo de passados que a máquina já não distingue, e projetar é decidir quais distinções do passado a continuação ainda pode cobrar. Onde a especificação diz "opcional, mas, se presente, obrigatório", existe um estado intermediário que nunca aceita: ele guarda um compromisso ainda não cumprido.
A terceira ideia dá um mínimo de estados, o **limite inferior**: vamos chamá-lo de **piso**. Dois prefixos são distinguíveis quando alguma continuação, a testemunha, põe exatamente um deles na linguagem, o conjunto das cadeias que valem. Com $k$ prefixos dois a dois distinguíveis, nenhum divide estado com outro, e toda máquina que reconhece a linguagem tem pelo menos $k$ estados. Nos parênteses balanceados, `(`, `((`, `(((` e assim por diante se separam dois a dois pela sequência de fechamentos de um deles. A família é infinita, nenhuma quantidade finita de estados basta, e nenhum autômato finito determinístico reconhece a linguagem.
## A máquina de números com sinal, executada
O alfabeto tem 13 símbolos: os dez dígitos, `+`, `-` e `.`. Os traços vêm de uma execução. Cada seta de `configuracoes` traz o símbolo lido, e em `--->` ele é o `-`; a posição conta a partir de zero.
```text
cadeia: "-240.75"
configuracoes: inicio ---> sinal -2-> inteiro -4-> inteiro -0-> inteiro -.-> apos_ponto -7-> fracao -5-> fracao
resultado: ACEITA
cadeia: "42."
configuracoes: inicio -4-> inteiro -2-> inteiro -.-> apos_ponto
resultado: RECUSA — consumiu a cadeia inteira e parou em estado nao final
cadeia: "++5"
configuracoes: inicio -+-> sinal -+-> erro -5-> erro
resultado: RECUSA — caiu no erro na posicao 1 (simbolo do alfabeto, transicao para o erro)
```
Em `++5`, o segundo `+` é símbolo do alfabeto, mas de `sinal` a transição dele vai ao erro. É a seta que o desenho omite e que, na função total, existe. Antes e depois do sinal a máquina espera um dígito, e ainda assim `sinal` pede estado próprio. A continuação `+5` separa as duas situações. Lida a partir de `inicio`, forma `+5`, que é número. Depois de um sinal, forma `++5`, que não é. O prefixo vazio e `+` são distinguíveis, e por isso ocupam estados diferentes.
## Onde a máquina contraria o palpite
O traço de `42.` desmonta dois atalhos. O primeiro aceita a cadeia por ter passado por $F$. `42.` atravessa `inteiro`, que aceita, e uma máquina com um sinalizador de "já passei por $F$" responderia sim, reconhecendo outra linguagem: a das cadeias com algum prefixo aceito. O segundo supõe que toda recusa passa pelo erro, e `42.` é recusada sem tocar nele: falta um dígito que ninguém escreveu.
Quem conta três ou quatro estados úteis na máquina de números deixa de fora os de compromisso pendente. Funda `apos_ponto` com `inteiro` e a máquina aceita `42.`. Devolva `+` e `-` a `inicio` e a tabela poupa uma linha, mas a máquina passa a aceitar `++5` e `+-5`.
A testemunha pode ser a cadeia vazia, $\varepsilon$, e é a primeira a tentar: ela separa `4` de `4.`, porque só `4` é número. A vazia também separa `4.` de `45`. Espere antes de encadear os dois pares e concluir que `4` e `45` se separam: os dois chegam a `inteiro`, e continuação nenhuma os distingue. O piso exige uma testemunha para cada par, e procurá-las é o primeiro passo do projeto: o desenho só mostra os estados já pensados, e a testemunha acha o que falta.
## Três previsões para conferir
*Responda antes de abrir cada bloco.*
Primeiro, simular. Que sequência de estados a máquina de números percorre sobre `7.2.`, e qual é o veredito?
**Resposta**
`inicio -7-> inteiro -.-> apos_ponto -2-> fracao -.-> erro`. Recusa, com queda no erro na posição 3: o segundo `.` pertence ao alfabeto, mas de `fracao` só o dígito leva adiante. O diagrama omite essa seta; a totalidade de $\delta$ a manda ao erro.
Depois, projetar. Sobre o alfabeto dos dez dígitos mais a letra `e`, uma especificação pede um ou mais dígitos seguidos, opcionalmente, de `e` e de um ou mais dígitos. Quantos estados úteis precisa ter uma máquina que a reconheça?
**Resposta**
Quatro. Os prefixos $\varepsilon$, `1`, `1e` e `1e1` são dois a dois distinguíveis. A testemunha vazia separa ($\varepsilon$, `1`), ($\varepsilon$, `1e1`), (`1`, `1e`) e (`1e`, `1e1`), porque só `1` e `1e1` pertencem à linguagem. A testemunha `e1` separa (`1`, `1e1`), e `1e1` separa ($\varepsilon$, `1e`): nos dois pares, `1e1` pertence e `1e1e1` não. Os quatro ainda podem virar cadeia aceita, então ocupam estados úteis.
Uma máquina com esse número aceita em `inteiro` e `expoente` e manda ao erro o que falta nesta lista: `inicio` vai a `inteiro` por dígito; `inteiro` fica em si por dígito e vai a `apos_e` pela letra `e`; `apos_e` vai a `expoente` por dígito; `expoente` fica em si por dígito.
Por fim, uma testemunha. Qual separa os prefixos `4` e `4.5` na máquina de números?
**Resposta**
Qualquer cadeia com dígitos opcionais, um ponto e ao menos um dígito depois dele, como `.5` ou `5.5`. `4` e `4.5` pertencem à linguagem, então a vazia falha, e dígitos também, porque `45` e `4.55` são aceitas. Com `.5`, `4.5` é aceita e `4.5.5` cai no erro no segundo ponto.
## Para ir além
No material, "Um modelo de neurônio que virou quíntupla" conta a origem do modelo, num artigo de 1943. "Sete passos para `valor_2`, e nenhum de volta" executa uma máquina como sequência de configurações. "O que a máquina precisa lembrar" demonstra o limite inferior e prova que os estados bastam. "A função total vira memória" mede a tabela em bytes, e "Três jeitos de dizer não" separa as três formas de recusa e a mensagem de cada uma.
## Definições e resultados formais, palavra por palavra
### Definição: Autômato finito determinístico
Um autômato finito determinístico é uma quíntupla $M = (Q, \Sigma, \delta, q_0, F)$. Nela, $Q$ é um conjunto finito e não vazio de estados e $\Sigma$ é um alfabeto finito. A função de transição é $\delta : Q \times \Sigma \to Q$. O estado inicial é $q_0 \in Q$, e $F \subseteq Q$ é o conjunto de estados de aceitação.
### Teorema: Completamento
Para todo autômato com função de transição parcial $\delta' : Q \times \Sigma \rightharpoonup Q$ existe um autômato com função de transição total que reconhece exatamente a mesma linguagem. Constrói-se $M = (Q \cup \{q_e\}, \Sigma, \delta, q_0, F)$, com $q_e \notin Q$. Define-se $\delta(q, a) = \delta'(q, a)$ onde $\delta'$ estiver definida. Nos demais casos, $\delta(q, a) = q_e$, inclusive para todo par $(q_e, a)$.
### Definição: Estado absorvente
Um estado $q \in Q$ é absorvente quando $\delta(q, a) = q$ para todo $a \in \Sigma$. Um estado absorvente que não pertence a $F$ chama-se estado de erro ou sumidouro; um estado absorvente que pertence a $F$ é um estado de aceitação irreversível.
### Definição: Configuração
Uma configuração de $M$ sobre uma cadeia é um par $(q, w) \in Q \times \Sigma^*$. Nele, $q$ é o estado corrente e $w$ é o sufixo da entrada ainda não consumido. A configuração inicial da máquina sobre a cadeia $w$ é $(q_0, w)$.
### Definição: Passo de computação
A relação de passo $\vdash_M$ entre configurações é definida por $(q, aw) \vdash_M (\delta(q,a), w)$ para todo $q \in Q$, $a \in \Sigma$ e $w \in \Sigma^*$. Denota-se por $\vdash_M^{*}$ o fecho reflexivo e transitivo de $\vdash_M$, isto é, a relação que vale entre duas configurações ligadas por zero ou mais passos.
### Definição: Função de transição estendida
A função $\hat{\delta} : Q \times \Sigma^* \to Q$ é definida por indução sobre a cadeia. O caso base é $\hat{\delta}(q, \varepsilon) = q$. O passo é $\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)$, para todo $w \in \Sigma^*$ e $a \in \Sigma$. Vale $\hat{\delta}(q,w) = p$ se e somente se $(q, w) \vdash_M^{*} (p, \varepsilon)$.
### Definição: Linguagem reconhecida
A linguagem reconhecida por $M$ é $L(M) = \{ w \in \Sigma^* : \hat{\delta}(q_0, w) \in F \}$. Uma linguagem $L$ é dita **regular** quando existe um autômato finito determinístico $M$ tal que $L = L(M)$.
### Definição: Prefixos distinguíveis
Dois prefixos $u, v \in \Sigma^*$ são distinguíveis com respeito a uma linguagem $L$ quando existe uma cadeia $z \in \Sigma^*$ com a propriedade a seguir. Exatamente uma das cadeias $uz$ e $vz$ pertence a $L$. Tal cadeia $z$ chama-se **testemunha** da distinção.
### Teorema: Limite inferior de estados
Se existem $k$ prefixos dois a dois distinguíveis com respeito a $L$, então todo autômato finito determinístico que reconhece $L$ tem pelo menos $k$ estados.
## Termos do módulo
- **Função de transição**: Regra que, dado o estado corrente e o símbolo lido, determina para onde a máquina vai. Sua versão estendida faz o mesmo para uma cadeia inteira, aplicando a regra símbolo a símbolo.
- **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, num papel em branco, tudo o que você lembra sobre autômatos finitos determinísticos: definições, propriedades, exemplos e contas. 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**
- Um autômato finito determinístico é a quíntupla $M = (Q, \Sigma, \delta, q_0, F)$: $Q$ finito e não vazio, $\Sigma$ alfabeto finito, $\delta : Q \times \Sigma \to Q$, $q_0 \in Q$ e $F \subseteq Q$.
- A função de transição é total: cada par de estado e símbolo tem um destino. $F = \emptyset$ e $F = Q$ são legítimos.
- O desenho com setas faltando abrevia uma máquina completa: o completamento acrescenta $q_e$, manda a ele toda transição omitida, inclusive as de $q_e$, e preserva a linguagem.
- Um estado é absorvente quando volta a si por todo símbolo. Fora de $F$, é estado de erro, e sem a absorção o completamento mudaria a linguagem; em $F$, é de aceitação irreversível.
- Uma configuração é o par do estado corrente com o sufixo ainda não consumido, e a inicial sobre $w$ é $(q_0, w)$; o já lido fica fora dela.
- Cada passo consome um símbolo, e toda configuração com sufixo não vazio tem exatamente uma seguinte: $n$ símbolos se leem em $n$ passos, sem retrocesso.
- A função estendida tem caso base $\hat{\delta}(q, \varepsilon) = q$ e passo $\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)$.
- $L(M) = \{ w \in \Sigma^* : \hat{\delta}(q_0, w) \in F \}$: decide só o estado alcançado depois da cadeia inteira, e por isso $\varepsilon \in L(M)$ se e somente se $q_0 \in F$. Regular é a linguagem que algum autômato finito determinístico reconhece.
- A máquina recusa de três formas: lendo símbolo do alfabeto cuja transição leva ao erro, lendo símbolo fora do alfabeto, ou consumindo a cadeia inteira e parando fora de $F$.
- Se $\hat{\delta}(q_0, u) = \hat{\delta}(q_0, v)$, então $uz$ e $vz$ recebem a mesma resposta para todo $z$: o estado resume os passados que a máquina deixou de distinguir.
- Cada "opcional, mas, se presente, obrigatório" da especificação pede um estado intermediário fora de $F$.
- Os prefixos $u$ e $v$ são distinguíveis quando alguma testemunha $z$ põe exatamente uma de $uz$ e $vz$ em $L$; $z$ pode ser $\varepsilon$, e $u$ e $v$ são cadeias quaisquer de $\Sigma^*$.
- Com $k$ prefixos dois a dois distinguíveis, todo autômato que reconhece $L$ tem pelo menos $k$ estados. O piso não garante a sua máquina: que ela reconhece $L$ se prova nela, por indução sobre o prefixo, com uma descrição para cada estado.
- A distinguibilidade não é transitiva: $u$ separado de $v$, e $v$ de $w$, não diz nada sobre $u$ e $w$.
- Quando os prefixos dois a dois distinguíveis formam família infinita, como `(`, `((`, `(((` nos parênteses balanceados, nenhum autômato finito determinístico reconhece a linguagem.
- Na matriz densa, a tabela tem $B(n,k,b) = n \cdot k \cdot b$ bytes para $n$ estados, o de erro incluído, $k$ símbolos e $b$ bytes por célula. Mapear byte em coluna troca as 256 colunas pelo alfabeto declarado, mais o vetor de colunas, de 256 entradas por autômato.
## 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 determinístico
- Função de transição
- Tabela de transição
- Estado de erro
- Estado absorvente
- Configuração
- Passo de computação
- Função de transição estendida
- Linguagem reconhecida
- Linguagem regular
- Prefixos distinguíveis
- Testemunha
- Limite inferior de estados
**As relações**
| De | Relação | Para |
| --- | --- | --- |
| Autômato finito determinístico | tem como componente | Função de transição |
| Função de transição | é armazenada na | Tabela de transição |
| Estado de erro | torna total a | Função de transição |
| Estado de erro | é um caso de | Estado absorvente |
| Tabela de transição | reserva uma linha ao | Estado de erro |
| Passo de computação | é uma relação entre | Configuração |
| Passo de computação | consulta a | Função de transição |
| Função de transição estendida | estende às cadeias a | Função de transição |
| Função de transição estendida | resume zero ou mais | Passo de computação |
| Linguagem reconhecida | é definida pela | Função de transição estendida |
| Linguagem regular | é reconhecida por | Autômato finito determinístico |
| Testemunha | separa dois | Prefixos distinguíveis |
| Limite inferior de estados | se demonstra com | Prefixos distinguíveis |
| Limite inferior de estados | vale para todo | Autômato finito determinístico |
## Não confunda
**Estado de erro** e **estado absorvente**: todo estado absorvente é um estado de erro?
**Resposta**
Absorvente é o estado que volta a si por todo símbolo do alfabeto. O estado de erro é o absorvente que fica fora de $F$; o absorvente que pertence a $F$ é um estado de aceitação irreversível. A máquina de um único estado $q$, com $F = Q = \{q\}$, reconhece $\Sigma^*$: $q$ é absorvente, porque toda transição volta a ele, e pertence a $F$, logo é absorvente sem ser estado de erro.
**Recusa** e **queda no estado de erro**: uma cadeia recusada passa necessariamente pelo estado de erro?
**Resposta**
A recusa se decide pelo estado alcançado depois da cadeia inteira, fora de $F$. Cair no erro é uma das maneiras de terminar ali, e a outra é consumir a cadeia sem tocá-lo. Na máquina de identificadores, cujo estado inicial não aceita, a cadeia vazia é recusada com zero passos. Na de números com sinal, `+` leva o peão de `inicio` a `sinal`, e ele para ali, sem passar pelo erro.
**Configuração** e **prefixo já lido**: duas execuções que leram prefixos diferentes podem estar na mesma configuração?
**Resposta**
Podem, porque a configuração é o par do estado corrente com o sufixo ainda não consumido, e o prefixo lido não entra nele. Na máquina de números com sinal, a execução sobre `4.5` chega, depois de um passo, a (`inteiro`, `.5`); a execução sobre `45.5` chega à mesma configuração depois de dois. Os prefixos lidos, `4` e `45`, diferem, e dali em diante as duas execuções coincidem até a resposta, aceita.
**Limite inferior de estados** e **suficiência dos estados**: exibir três prefixos dois a dois distinguíveis e uma máquina de três estados demonstra que a máquina reconhece a linguagem?
**Resposta**
Demonstra só o piso: toda máquina para a linguagem precisa de ao menos três estados. Que a sua a reconhece se prova sobre ela, por indução sobre o prefixo, com uma descrição para cada estado. Nos identificadores (letra minúscula seguida de letras, dígitos ou sublinhado), $\varepsilon$, `a` e `1` se separam dois a dois: $\varepsilon$ separa `a` dos outros dois, e `a` separa $\varepsilon$ de `1`, porque `a` é identificador e `1a` não é. Uma máquina de três estados, contando o de erro, que levasse o dígito inicial de `inicio` a `corpo` respeitaria o piso e aceitaria `1`.
## Perguntas em três níveis
### Lembrar
O que é uma configuração de $M$, e como se define a relação de passo entre configurações?
**Resposta**
Uma configuração de $M$ sobre uma cadeia é um par $(q, w) \in Q \times \Sigma^*$. Nele, $q$ é o estado corrente e $w$ é o sufixo da entrada ainda não consumido. A configuração inicial da máquina sobre a cadeia $w$ é $(q_0, w)$.
A relação de passo $\vdash_M$ entre configurações é definida por $(q, aw) \vdash_M (\delta(q,a), w)$ para todo $q \in Q$, $a \in \Sigma$ e $w \in \Sigma^*$.
Como se define a linguagem reconhecida por $M$, e quando uma linguagem é regular?
**Resposta**
A linguagem reconhecida por $M$ é $L(M) = \{ w \in \Sigma^* : \hat{\delta}(q_0, w) \in F \}$. Uma linguagem $L$ é dita **regular** quando existe um autômato finito determinístico $M$ tal que $L = L(M)$.
O que torna dois prefixos distinguíveis, e que piso de estados eles impõem?
**Resposta**
Dois prefixos $u, v \in \Sigma^*$ são distinguíveis com respeito a uma linguagem $L$ quando existe uma cadeia $z \in \Sigma^*$ com a propriedade a seguir. Exatamente uma das cadeias $uz$ e $vz$ pertence a $L$. Tal cadeia $z$ chama-se **testemunha** da distinção.
Se existem $k$ prefixos dois a dois distinguíveis com respeito a $L$, então todo autômato finito determinístico que reconhece $L$ tem pelo menos $k$ estados.
### Explicar
Por que o estado de erro acrescentado no completamento precisa ser absorvente?
**Resposta**
Suponha que, de $q_e$, algum símbolo levasse a um estado útil. Então uma cadeia que tinha caído no erro poderia sair dele e terminar em $F$: a máquina completa aceitaria o que a parcial recusava, e o completamento deixaria de ser abreviação para virar alteração. Na máquina de identificadores, se $q_e$ fosse a `corpo` pela letra `a`, a cadeia `1a` seria aceita, porque `1` leva ao erro e o `a` traria o peão de volta a `corpo`.
Por que a leitura de uma cadeia de comprimento $n$ termina em exatamente $n$ passos, sem nunca voltar atrás?
**Resposta**
Cada passo consome exatamente um símbolo do sufixo, e enquanto houver símbolo existe exatamente uma configuração seguinte, porque $\delta$ é total e devolve um único estado. Sem escolha, não há caminho alternativo a tentar nem por onde voltar. O sufixo se esvazia depois de $n$ passos, qualquer que seja a cadeia, e cada passo é uma consulta a $\delta$ e uma atribuição: com consulta em tempo constante, o custo é linear em $n$.
Se dois prefixos levam a máquina ao mesmo estado, por que nenhuma continuação os separa depois?
**Resposta**
Ler $uz$ é ler $u$ e, do estado alcançado, ler $z$: $\hat{\delta}(q_0, uz) = \hat{\delta}(\hat{\delta}(q_0, u), z)$, por indução sobre $z$ na definição de $\hat{\delta}$. Se $\hat{\delta}(q_0, u) = \hat{\delta}(q_0, v) = p$, as duas leituras continuam de $p$ e terminam no mesmo estado $\hat{\delta}(p, z)$, que está ou não está em $F$ para as duas ao mesmo tempo. Na máquina de números com sinal, `+3` e `27` chegam a `inteiro`, e daí em diante nenhuma continuação separa as duas: com `.5` as duas são aceitas, com `.` as duas são recusadas.
### Aplicar
A máquina de números com sinal tem alfabeto de 13 símbolos (os dez dígitos, `+`, `-` e `.`) e reconhece sinal opcional, parte inteira e parte fracionária opcional: a parte inteira tem um ou mais dígitos, e a fracionária, quando existe, é um ponto e um ou mais dígitos. Para cada cadeia, `-0.5`, `5-`, `+` e `1e5`, diga se ela é aceita e, se for recusada, por qual das três formas, com a posição contada a partir de zero.
**Resposta**
`-0.5` é aceita: `inicio`, `sinal`, `inteiro`, `apos_ponto`, `fracao`. `5-` cai no erro na posição 1, por símbolo do alfabeto: de `inteiro`, o `-` leva ao erro. `+` consome a cadeia inteira e para em `sinal`, fora de $F$, sem passar pelo erro. `1e5` cai no erro na posição 1, por símbolo fora do alfabeto, e os passos seguintes ficam no erro.
Sobre o alfabeto $\{a, b\}$, a linguagem reúne toda cadeia em que `ab` aparece como subcadeia. Contando todos os estados, quantos tem a menor máquina que a reconhece, e por que nenhuma tem menos?
**Resposta**
Três. Os prefixos $\varepsilon$, `a` e `ab` se separam dois a dois. A testemunha vazia separa `ab` de cada um dos outros dois, e uma testemunha que separa $\varepsilon$ de `a` é `b`, porque `ab` pertence à linguagem e `b` não. Pelo limite inferior, nenhuma máquina tem menos de três estados.
Três bastam: $s_0$, nenhum `ab` e a cadeia não termina em `a`; $s_1$, nenhum `ab` e termina em `a`; $s_2$, já contém `ab`, único em $F$. Pelo `a`, $s_0$ e $s_1$ vão a $s_1$; pelo `b`, $s_0$ fica em $s_0$ e $s_1$ vai a $s_2$; $s_2$ volta a si pelos dois.
A máquina de identificadores tem dois estados úteis e alfabeto declarado de 37 símbolos: as 26 letras minúsculas, os dez dígitos e o sublinhado. Pela fórmula $B(n,k,b)$, quantos bytes ocupa a tabela se cada destino ocupar 2 bytes, e quantos ocuparia com uma coluna para cada um dos 256 valores de um byte?
**Resposta**
Com o estado de erro, $n = 3$. A tabela ocupa $3 \cdot 37 \cdot 2 = 222$ bytes, e indexada pelo byte ocuparia $3 \cdot 256 \cdot 2 = 1.536$ bytes, cerca de sete vezes mais, qualquer que seja $b$. A comparação é só de tabela: o mapeamento de byte para coluna acrescenta o vetor de colunas, de 256 entradas por autômato, que a fórmula não conta.
===== FIM DO MATERIAL =====