Autômatos finitos determinísticos — Atlas

O módulo inteiro em oito peças visuais. Cada uma olha o mesmo conteúdo por um lado: o resumo desenhado, os procedimentos passo a passo, os cartões para treinar de memória, o módulo contado em quadros, o mapa dos tópicos, o painel que junta tudo, a rede de conceitos e a folha para consultar na hora.

Resumo ilustrado

Resumo ilustrado em nove quadros. 1, o tabuleiro: casa é estado, peão é onde a máquina está, seta é transição, buraco é estado de erro e foto é configuração; sem bloco de anotações, o que a máquina sabe do que leu é a casa do peão. 2, a quíntupla M = (Q, Σ, δ, q0, F), com δ : Q × Σ → Q total, um estado inicial só, e F podendo ser vazio ou o próprio Q. 3, o buraco: inicio vai a corpo por letra e ao erro por dígito ou sublinhado; o erro é absorvente; completar acrescenta um estado e as setas que faltam, 37 + 11 = 48 setas novas no identificador; absorvente em F é aceitação irreversível. 4, a foto e o passo: (q, w) é o estado e o que falta ler; (q, aw) leva a (δ(q, a), w); cada passo consome exatamente um símbolo, n símbolos custam exatamente n passos, nada por onde voltar, e o que já foi lido fica fora da foto. 5, aceitar: o estado depois da cadeia inteira está em F; 42. para em apos_ponto e é recusada, porque passar por F no meio não conta; a cadeia vazia é aceita se e só se q0 está em F; L(M) é regular pela definição. 6, um estado é uma memória: a e abc9_ chegam a corpo e recebem a mesma resposta para toda continuação; quem só sabe em que estado está não sabe quantas vezes já entrou nele. 7, o piso: k prefixos distinguíveis dois a dois obrigam pelo menos k estados; a testemunha z deixa só uma de uz e vz em L e pode ser a cadeia vazia; família infinita, como os parênteses, mostra que a linguagem não é regular; o piso mostra que nenhum estado sobra, e que nenhum falta se prova na máquina. 8, o preço: B(n, k, b) = n · k · b; identificador 888, número 624 e comentário 896 bytes de tabela, a 8 bytes por destino; vetor de colunas de 2.048 bytes por autômato; matriz densa com consulta em tempo constante; o que a definição não faz, o código faz por ela, e cobra. 9, três recusas: do alfabeto e levando ao erro, 2valor na posição 0; fora do alfabeto, //OK na posição 2; parando fora de F, 42., sem queda; recusar é responder, e a mensagem útil diz o que se esperava naquela posição.
Figura 1: O módulo numa página: o tabuleiro, a quíntupla, o estado de erro, a foto e o passo, a aceitação, o estado como memória, o piso de estados, o preço da tabela e as três recusas.

Fluxogramas

Cinco procedimentos do módulo. Siga cada um com o lápis, sobre uma máquina ou uma especificação sua.

Completar o desenho e conferir a tabela

Deixar setas de fora de um desenho é declarar que todos aqueles pares vão para o erro. A conferência mostra se era isso mesmo.

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    E["desenho com setas faltando: acrescente<br/>o estado de erro, fora da aceitação"]
    T["escreva a tabela inteira: uma linha por estado,<br/>inclusive o de erro, e uma coluna por símbolo;<br/>todo par sem seta recebe o erro como destino"]
    Q1{"(1) cada célula que aponta<br/>para o erro devia mesmo ir para lá?"}
    X["a máquina desenhada é outra:<br/>corrija a seta daquele par"]
    Q2{"(2) a linha do erro aponta,<br/>inteira, para o próprio erro?"}
    Y["uma saída do erro faria aceitar<br/>cadeia que o desenho recusava"]
    OK["a tabela descreve a máquina que você tinha em mente,<br/>e ela reconhece a mesma linguagem do desenho"]

    E --> T --> Q1
    Q1 -->|"não"| X --> T
    Q1 -->|"sim"| Q2
    Q2 -->|"não"| Y --> T
    Q2 -->|"sim"| OK

Figura 2: O completamento e as duas perguntas da conferência. A conferência diz se o desenho é a máquina que você tinha em mente; se a linguagem é a certa depende de as situações terem sido bem escolhidas.

Executar a máquina sobre uma cadeia

Um símbolo por passo, até o fim da cadeia, mesmo depois de uma queda no erro. A aceitação se testa uma vez só, com a cadeia acabada.

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    I["o peão no estado inicial;<br/>a cadeia inteira por ler"]
    S{"sobra símbolo<br/>por ler?"}
    C{"o símbolo<br/>tem coluna?"}
    FA["fora do alfabeto declarado:<br/>anote a posição, se é a primeira<br/>queda; o peão vai ao erro"]
    Q{"a célula leva<br/>ao erro pela<br/>primeira vez?"}
    QA["anote a posição da queda"]
    N["o peão vai ao destino;<br/>avance uma posição"]
    FIM["lida a cadeia inteira:<br/>o veredito"]

    I --> S
    S -->|"sim"| C
    C -->|"não"| FA --> S
    C -->|"sim"| Q
    Q -->|"sim"| QA --> N
    Q -->|"não"| N
    N --> S
    S -->|"não"| FIM

Figura 3: A leitura, como o projeto de referência a executa: um símbolo por passo, com a primeira queda anotada. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    L["a cadeia inteira lida"]
    F{"o estado<br/>alcançado<br/>está em F?"}
    A["aceita"]
    H{"houve queda<br/>anotada?"}
    R1["recusa com culpado:<br/>mostre a posição; diga se<br/>o símbolo é do alfabeto ou não"]
    R3["recusa sem queda:<br/>a cadeia parou cedo;<br/>diga o que se esperava"]

    L --> F
    F -->|"sim"| A
    F -->|"não"| H
    H -->|"sim"| R1
    H -->|"não"| R3

Figura 4: O veredito, com a cadeia acabada. A recusa que nunca passa pelo erro é a que não tem culpado.

Projetar a máquina a partir da especificação

A pergunta de fundo é uma só: que informações do passado a máquina tem de carregar adiante?

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    E["especificação em português"]
    FIN{"é finito?"}
    NAO["nenhuma máquina<br/>finita serve: mostre<br/>uma família infinita<br/>de prefixos"]
    S1["(1) liste as situações<br/>que a especificação<br/>obriga a distinguir"]
    S2["(2) nomeie cada uma<br/>pelo que ela lembra:<br/>«abri aspas e<br/>ainda não fechei»"]
    PAR{"respostas<br/>diferentes?"}
    DOIS["ficam dois estados"]
    UM["cabem num estado só"]
    S3["(3) decida a situação<br/>seguinte para cada<br/>situação e cada símbolo,<br/>sem par em branco"]
    S4["(4) marque as situações<br/>em que parar quer dizer<br/>sim; o que sobra sem<br/>nome é o erro"]

    E -->|"o que a máquina<br/>precisa lembrar"| FIN
    FIN -->|"não"| NAO
    FIN -->|"sim"| S1 --> S2 -->|"duas situações,<br/>a mesma continuação"| PAR
    PAR -->|"sim"| DOIS --> S3
    PAR -->|"não"| UM --> S3
    S3 --> S4

Figura 5: As quatro etapas do projeto. Situações que respondem de modo diferente à mesma continuação precisam de estados diferentes. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    M["a máquina das etapas (1) a (4)"]
    FECHA{"a máquina não fecha,<br/>ou falha num teste?"}
    PEAO{"passe o peão por duas cadeias que deviam<br/>ter tratamento diferente: chegam ao mesmo estado?"}
    FALTA["falta uma distinção: ela é o nome<br/>do estado novo; volte à etapa (2)"]
    SETA["o problema está nas setas:<br/>volte à etapa (3)"]
    OK["máquina projetada"]

    M --> FECHA
    FECHA -->|"não"| OK
    FECHA -->|"sim"| PEAO
    PEAO -->|"sim"| FALTA
    PEAO -->|"não"| SETA

Figura 6: O diagnóstico da máquina que não fecha, ou que falha num teste: ou falta uma distinção, ou o problema está nas setas.

Achar o piso de estados com testemunhas

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    P["para a linguagem L,<br/>escolha prefixos de Σ*,<br/>inclusive os que<br/>levam ao erro"]
    PAR["tome um par u, v<br/>ainda não separado"]
    Z{"alguma z separa?<br/>comece pela vazia"}
    TROCA["tentativa que falha<br/>não prova nada: tente<br/>outra z, ou troque<br/>um dos prefixos"]
    TODOS{"todos os pares<br/>separados?"}
    K["k prefixos separados<br/>dois a dois: toda<br/>máquina para L tem<br/>pelo menos k estados"]
    INF{"a família pode<br/>crescer sem fim?"}
    NR["como nos parênteses<br/>balanceados: nenhuma<br/>máquina finita serve,<br/>L não é regular"]
    SUF["o piso mostra que<br/>nenhum estado sobra;<br/>que nenhum falta se<br/>prova na máquina"]

    P --> PAR --> Z
    Z -->|"sim: só uma de<br/>uz e vz está em L"| TODOS
    Z -->|"não achei"| TROCA --> PAR
    TODOS -->|"não"| PAR
    TODOS -->|"sim"| K --> INF
    INF -->|"sim"| NR
    INF -->|"não"| SUF

Figura 7: O limite inferior aplicado par a par. Comece pela testemunha vazia: ela separa todo par em que só um dos prefixos pertence à linguagem.

Calcular o tamanho da tabela e decidir

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    F["B = n · k · b<br/>n: os estados, com o de erro<br/>k: as colunas do alfabeto declarado<br/>b: os bytes de um destino; o número de estados tem de caber nele"]
    V["some o vetor de colunas:<br/>256 entradas por autômato"]
    D["conte as células que vão para o erro,<br/>e a fração da tabela que elas ocupam"]
    A["anote o tamanho em que a decisão se refaz"]
    Q{"fração alta?"}
    E{"a escala cresce?"}
    OK["aceite a tabela"]
    R["refaça a decisão: primeiro as alternativas<br/>que recuperam memória sem perder<br/>a consulta em tempo constante"]

    F --> V --> D --> A --> Q
    Q -->|"não"| OK
    Q -->|"sim"| E
    E -->|"não"| OK
    E -->|"sim"| R

Figura 8: A conta antes do programa: três fatores, o vetor de colunas e a fração que guarda o mesmo valor. Fração alta em escala pequena: aceite a tabela.

Cartões de memória

Leia a frente, diga a resposta em voz alta ou escreva no papel, e só então vire o cartão.

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.
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.

História em quadros

O módulo contado do começo ao fim, um quadro por passo, na ordem em que o livro avança.

História em quadros, quinze quadros em cinco linhas. 1, um modelo de neurônio: 1943, McCulloch e Pitts, o modelo de estados finitos; dezembro de 1951, Kleene, a notação regular; 1956, o memorando publicado em Automata Studies; o assunto dos dois textos é o sistema nervoso; do artigo vem o modelo, e de Kleene a notação e o modelo como objeto matemático. 2, a quíntupla M = (Q, Σ, δ, q0, F): estados, alfabeto, transição, inicial e aceitação, com δ : Q × Σ → Q, um destino para cada par de estado e símbolo. 3, nenhum par sem destino: inicio vai a corpo pelas 26 letras e ao erro por dígito ou sublinhado, a seta que o desenho omite; o erro volta a si pelos 37 símbolos; o desenho com setas faltando abrevia a máquina completa. 4, oito fotos de valor_2: de (inicio, valor_2), pelo v, a (corpo, alor_2), cinco passos, e de (corpo, 2), pelo 2, a (corpo, ε); a foto é o estado mais o que falta ler, sete passos e nenhum de volta. 5, conta onde a cadeia termina: 42. vai de inicio a inteiro, inteiro e apos_ponto, para fora de F e é recusada; passar por inteiro não basta; a cadeia vazia é aceita se e só se q0 está em F; um sinalizador de já passei por F reconhece outra linguagem. 6, um estado é uma memória: a e abc9_ chegam a corpo; quem só sabe em que estado está não sabe quantas vezes já entrou nele. 7, contar as viradas: identificador 1 + 1 = 2 estados úteis, comentário de linha 2 + 1 = 3, número com sinal 4 + 1 = 5; o mais um é a situação inicial, e a soma serve para conferir. 8, o sinal pede um estado: inicio vai a sinal por mais ou menos, e sinal a inteiro por dígito; a testemunha +5 separa, porque +5 é número e ++5 não é; sem o estado sinal, a máquina aceitaria ++5; o sinal e o ponto deixam um compromisso, um estado intermediário que nunca é de aceitação. 9, uma testemunha por par: os prefixos ε, +, 4, 4. e 4.5, dez pares e quatro testemunhas, +5, 5.5, .5 e a vazia; piso de 5 estados úteis. 10, a máquina que não fecha: os prefixos (, ((, (((, sem fim; (( e ((( se separam por )); mais prefixos do que estados obrigam dois a dividir um estado, e nenhuma máquina finita serve. 11, a tabela vira memória: uma grade com linha por estado e coluna por símbolo, índice q · k + c, e 3 × 13 + 7 = 46 para apos_ponto lendo 7; o mapa esparso guarda só o que não vai ao erro; a matriz densa consulta em tempo constante. 12, a coluna vem do vetor: o byte, de 256 valores, passa pelo vetor de colunas e vira uma das 13 colunas da máquina de número; 256 colunas por estado contra 13; o vetor ocupa 2.048 bytes, um por autômato; na máquina de número, 12.288 contra 2.672 bytes. 13, três fatores e uma multiplicação: B(n, k, b) = n · k · b; identificador 3 × 37 × 8 = 888, número com sinal 6 × 13 × 8 = 624, comentário de linha 4 × 28 × 8 = 896; no comentário, 82 de 112 células dizem não, 656 bytes; o que a definição não faz, o código faz por ela, e cobra. 14, três jeitos de dizer não: 2valor cai na posição 0 com um símbolo do alfabeto; //OK cai na posição 2, com o O fora do alfabeto; 42. não cai e para fora de F; a mensagem útil diz o que se esperava. 15, uma tabela que diz não: a máquina feita à mão e medida leva ao módulo 04, a máquina da expressão, ao 05, determinizar e reduzir, e ao 06, a segunda rota; lida a primeira letra, a tabela já não sabe quantas vieram depois.
Figura 9: O módulo do começo ao fim, em quinze quadros: o modelo de neurônio, a quíntupla, a função total, as oito fotos de valor_2, a aceitação no fim da cadeia, o estado como memória, as viradas, o estado do sinal, as testemunhas, a máquina que não fecha, a matriz densa, o vetor de colunas, a fórmula, as três recusas e a tabela que diz não.

Mapa mental

Os tópicos do módulo, do centro para fora, na ordem do livro.

Mapa mental com o título do módulo no centro e nove ramos. Um modelo de neurônio: McCulloch e Pitts em 1943, o modelo; Kleene em dezembro de 1951, a notação; o memorando publicado em 1956. A máquina como quíntupla: os cinco componentes, a função de transição é total, o estado de erro absorvente. O reconhecimento: a configuração, estado e o que falta ler; o passo, um símbolo e nenhum de volta; a função de transição estendida; a linguagem reconhecida. Projetar a partir da especificação: um estado é uma memória; identificador, número e comentário; quando a máquina não fecha. Por que os estados bastam: estados como classes de passados; o limite inferior e o piso. A tabela de transição: a matriz densa; o mapa esparso guarda menos; a coluna vem do vetor de colunas. O preço, medido: B(n, k, b) = n · k · b; o desperdício, e por que se aceita; o que a fórmula prevê. As formas de recusar: três recusas distintas; recusar é uma resposta; a mensagem que ajuda. Memória que custa bytes: a tabela que diz não; três adiamentos, para os módulos 04, 05 e 06.
Figura 10: Os tópicos e subtópicos do módulo, em árvore, na ordem do livro, em sentido horário a partir do alto, à direita.

Painel do conhecimento

Conceitos

  • Autômato finito determinístico: a quíntupla M = (Q, \Sigma, \delta, q_0, F), com a função de transição \delta : Q \times \Sigma \to Q total.
  • Estado de erro: o estado absorvente fora de F; o completamento o acrescenta sem mudar a linguagem.
  • Configuração: o par (q, w), o estado e o que falta ler.
  • Linguagem reconhecida, L(M): as cadeias que, lidas inteiras, levam o peão a F; é regular por definição.
  • Prefixos distinguíveis: separados por uma testemunha; k deles, dois a dois, dão o piso de k estados.
  • Tabela de transição: a função total guardada em memória, que custa B(n,k,b) = n \cdot k \cdot b bytes na matriz densa.

Exemplos

  • valor_2: aceita, em oito configurações.
  • 2valor: recusa, com queda no erro na posição 0.
  • 42.: recusa sem cair no erro, parada em apos_ponto.
  • ++5: recusa na posição 1; o segundo + encontra o peão em sinal.
  • Identificador: dois estados úteis; número com sinal: cinco; comentário de linha: três.

Diagrama

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    I["inicio<br/>não aceita"] -->|"+&nbsp;-"| S["sinal<br/>não aceita"]
    I -->|"dígito"| N["inteiro<br/>aceita"]
    S -->|"dígito"| N
    N -->|"dígito"| N
    N -->|"ponto (.)"| P["apos_ponto<br/>não aceita"]
    P -->|"dígito"| FR["fracao<br/>aceita"]
    FR -->|"dígito"| FR

Figura 11: A máquina de números com sinal: os cinco estados úteis. As setas que o desenho não mostra vão ao estado de erro.

Evidências

  • 1943: McCulloch e Pitts publicam, no The Bulletin of Mathematical Biophysics, um modelo do sistema nervoso com estados em número finito.
  • Dezembro de 1951: Kleene escreve o memorando RM-704, da RAND, com a notação das expressões regulares; o texto sai em livro em 1956.
  • 1957 e 1958: Myhill e Nerode chegam ao resultado completo sobre o número de estados, cada um em separado; a contribuição de Myhill está num relatório técnico de circulação restrita.
  • As contagens das três máquinas (células, bytes, transições que não vão ao erro) são as que o programa do projeto de referência calcula e imprime.

Referências

  • McCulloch e Pitts, A logical calculus of the ideas immanent in nervous activity, The Bulletin of Mathematical Biophysics, v. 5, n. 4, p. 115–133, 1943.
  • Kleene, Representation of events in nerve nets and finite automata, em Automata Studies, Princeton University Press, 1956, p. 3–41.
  • Nerode, Linear automaton transformations, Proceedings of the American Mathematical Society, v. 9, n. 4, p. 541–544, 1958.
  • Rabin e Scott, Finite automata and their decision problems, IBM Journal of Research and Development, v. 3, n. 2, p. 114–125, 1959.
  • Leitura complementar: Hopcroft, Motwani e Ullman; Menezes (Grupo A, 2011).

Aplicações

  • Um reconhecedor chamado sobre texto qualquer: recusar é o funcionamento normal, e num sistema que testa vários padrões na mesma posição o padrão que falha cede a vez.
  • No projeto de referência, cada tabela se calcula antes de se escrever: 888, 624 e 896 bytes.
  • As tarefas do módulo: decidir a representação da função de transição, com a conta, e executar uma máquina descrita à mão.
  • Adiante: a máquina construída a partir da expressão (04), a determinização e a redução de estados (05), a segunda rota para provar que uma linguagem não é regular (06).

Mapa conceitual

DicaAntes de olhar

Escreva num papel: autômato finito determinístico, função de transição, estados, completamento, estado de erro, estados de aceitação, configuração, passo de computação, linguagem reconhecida, linguagem regular, recusa, prefixos distinguíveis, testemunha, limite inferior, tabela de transição, matriz densa, vetor de colunas, B(n,k,b). Ligue os conceitos com setas, e escreva em cada seta um verbo que diga qual é a relação. Depois compare com o mapa.

Mapa conceitual. O autômato finito determinístico tem como componente a função de transição e reconhece a sua linguagem reconhecida, que é, por definição, uma linguagem regular, e reúne as cadeias que, lidas inteiras, param nos estados de aceitação. A função de transição escolhe o próximo entre os estados. O completamento torna total a função de transição e acrescenta o estado de erro, que é absorvente e fica fora dos estados de aceitação, e leva sempre à recusa; a recusa acontece quando a cadeia termina fora dos estados de aceitação. A configuração guarda, com o sufixo não lido, um dos estados. O passo de computação consome um símbolo e troca a configuração, e consulta a função de transição. A tabela de transição guarda em memória a função de transição; a matriz densa guarda inteira a tabela de transição; o vetor de colunas dá a coluna de cada byte à matriz densa; B(n, k, b) mede em bytes a matriz densa e multiplica o número de estados. Os prefixos distinguíveis são separados por uma testemunha e, tomados dois a dois, fixam o limite inferior, que dá o piso do número de estados.
Figura 12: Os conceitos do módulo ligados por frases de ligação. Cada seta, lida da origem ao destino, é uma afirmação do módulo.

Folha de consulta

A quíntupla

  • M = (Q, \Sigma, \delta, q_0, F): estados, alfabeto, transição, estado inicial, estados de aceitação
  • \delta : Q \times \Sigma \to Q é total: n \cdot k valores, para n estados e k símbolos
  • um estado inicial só; F = \emptyset e F = Q são legítimos
  • completar: um estado de erro a mais, com as suas \lvert\Sigma\rvert setas, e destino para cada par sem seta
  • absorvente fora de F: estado de erro; em F: aceitação irreversível

Executar e aceitar

  • configuração: (q, w); a inicial é (q_0, w)
  • passo: (q, aw) \vdash_M (\delta(q,a), w)
  • \hat{\delta}(q, \varepsilon) = q; \hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)
  • w \in L(M) quando \hat{\delta}(q_0, w) \in F
  • \varepsilon \in L(M) se e somente se q_0 \in F
  • n símbolos: exatamente n passos, aceita ou recusada

Projetar

    1. liste as situações; (2) nomeie cada uma pelo que ela lembra; (3) dê destino a cada par; (4) marque as de aceitação
  • símbolo que exige o que só vem depois: um estado intermediário que nunca é de aceitação
  • viradas mais a situação inicial: identificador 1 + 1 = 2, comentário de linha 2 + 1 = 3, número com sinal 4 + 1 = 5 estados úteis
  • a soma confere uma máquina projetada; ela não é fórmula geral

O piso

  • u e v distinguíveis: existe z com exatamente uma de uz e vz em L
  • a testemunha z pode ser \varepsilon
  • k prefixos distinguíveis dois a dois: todo autômato para L tem pelo menos k estados, contado o de erro se algum prefixo levar a ele
  • número com sinal: \varepsilon, +, 4, 4., 4.5; testemunhas +5, 5.5, .5 e \varepsilon
  • família infinita de prefixos dois a dois distinguíveis: a linguagem não é regular

Contas da tabela

Máquina n k Células Bytes Não-erro
identificador 3 37 111 888 63
número com sinal 6 13 78 624 53
comentário de linha 4 28 112 896 30
  • B(n,k,b) = n \cdot k \cdot b, com n contando o estado de erro e b = 8 bytes por destino
  • a outra escrita: (n+1) \times m, com n estados úteis e m símbolos
  • índice da célula: q \cdot k + c
  • vetor de colunas: 256 entradas por autômato, 256 \times 8 = 2.048 bytes
  • destinos de 2 bytes: no máximo 65.536 estados

Três recusas

  • símbolo do alfabeto cuja transição leva ao erro: 2valor, posição 0; /x, posição 1
  • símbolo fora do alfabeto declarado: //OK, posição 2
  • cadeia inteira lida, parada fora de F: 42., sem queda
  • a mensagem útil diz o que se esperava: «esperava-se um dígito após o ponto decimal»

Erros previsíveis

  • «a função de transição pode ser parcial»: a definição a exige total; o desenho com setas faltando é abreviação, e o completamento a legitima
  • «todo estado absorvente é estado de erro»: o absorvente em F é aceitação irreversível
  • «aceita se passar por um estado de aceitação»: vale o estado depois da cadeia inteira, e 42. é recusada
  • «recusa implica cair no erro»: 42. é recusada sem cair
  • «a testemunha tem de ser não vazia»: \varepsilon separa sempre que só um dos dois prefixos está em L
  • «a distinguibilidade é transitiva»: exija a separação dois a dois
  • «k prefixos distinguíveis provam que k estados bastam»: provam só que nenhum sobra
  • «ler o sinal não cria estado»: +5 separa o início do estado sinal
  • «a matriz densa economiza memória»: ela perde em memória para o mapa esparso e ganha no custo por símbolo consumido