%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
I["leia o próximo caractere"]
H{"ele cabe na hipótese<br/>que você escolheu?"}
S["siga lendo"]
V["volte ao começo do trecho:<br/>é o retrocesso"]
O{"resta outra hipótese,<br/>como dois trechos colados?"}
R["recuse, e diga a linha<br/>e a coluna do trecho"]
N["não conserte por conta própria:<br/>x3 e 3 * x dão programas diferentes"]
I --> H
H -->|"sim"| S
S --> I
H -->|"não"| V
V --> O
O -->|"sim, tente"| I
O -->|"não"| R
R --> N
Linguagens formais e a arquitetura de um compilador — 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
Fluxogramas
Dez procedimentos do módulo. Siga cada um com o lápis, sobre um caso seu.
Ler um trecho e decidir se ele passa
Experimente com 3x, numa linguagem em que número só tem dígitos e nome de variável começa por letra.
Unir e concatenar duas linguagens
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
A["duas linguagens: L₁ e L₂"]
Q{"que operação?"}
U["união: junte as cadeias que estão<br/>em L₁ ou em L₂"]
P["concatenação: forme os pares,<br/>uma cadeia de L₁ e uma de L₂, nessa ordem"]
C["cole cada par numa cadeia só"]
D["cadeia repetida conta uma vez:<br/>é a colisão"]
R["resultado: um conjunto de cadeias,<br/>com no máximo |L₁| · |L₂| delas"]
A --> Q
Q -->|"união"| U
Q -->|"concatenação"| P
P --> C --> D --> R
ab saiu de dois pares.
Montar o fecho com o acumulador e o teto
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
T["receba L e um teto de comprimento"]
Z["acumulador no nível 0: {ε}, e não ∅"]
G["guarde o acumulador no resultado"]
N["próximo nível: concatene o acumulador com L"]
F["descarte as cadeias maiores que o teto<br/>e as que já estão guardadas"]
Q{"sobrou alguma cadeia nova?"}
A["o acumulador passa a ser as novidades"]
P["pare: o resultado é a parte<br/>do fecho que cabe no teto"]
T --> Z --> G --> N --> F --> Q
Q -->|"sim"| A
A --> G
Q -->|"não"| P
Derivar uma cadeia e montar a árvore
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
S["comece pelo símbolo inicial, E"]
Q{"sobrou algum<br/>não terminal?"}
E["escolha um não terminal e uma produção<br/>que tenha ele do lado esquerdo"]
T["troque o não terminal pelo lado direito;<br/>anote a troca com =>"]
A["na árvore: ligue o nó trocado<br/>aos símbolos que entraram, em ordem"]
F["fim: só terminais, uma cadeia da linguagem"]
L["leia as folhas da esquerda para a direita:<br/>é a cadeia derivada"]
S --> Q
Q -->|"sim"| E
E --> T --> A --> Q
Q -->|"não"| F
F --> L
E → E + T, E → T, T → ( E ) e T → a, a cadeia (a+a) sai em seis trocas, e a árvore tem onze nós, cinco deles folhas.
Desfazer uma abreviação da BNF
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
R["uma produção abreviada"]
Q{"que abreviação ela usa?"}
B["a barra, lida como ou:<br/>E -> E + T #124; T"]
B2["uma produção para cada alternativa:<br/>E -> E + T e E -> T"]
S["o asterisco, zero ou mais vezes:<br/>decl -> item*"]
S2["duas produções, por recursão:<br/>decl -> ε e decl -> item decl"]
M["mesma linguagem, escrita por extenso:<br/>a abreviação não acrescentou poder"]
R --> Q
Q -->|"barra"| B
B --> B2
Q -->|"asterisco"| S
S --> S2
B2 --> M
S2 --> M
Montar a linguagem que nenhuma fila contém
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
F["suponha uma fila com todas as linguagens:<br/>L₁, L₂, L₃, …"]
N["tome o lugar n"]
C["pegue a cadeia do lugar n<br/>na fila das cadeias"]
Q{"ela está em Lₙ?"}
D1["ela fica fora de D"]
D2["ela entra em D"]
P["passe ao lugar n + 1"]
R["D é linguagem, mas difere de cada Lₙ<br/>na cadeia do lugar n: não está na fila"]
F --> N --> C --> Q
Q -->|"sim"| D1
Q -->|"não"| D2
D1 --> P
D2 --> P
P --> N
P -.->|"para todo n"| R
Mostrar que k estados não bastam
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
K["fixe uma máquina de k estados<br/>para os parênteses balanceados"]
E["dê a ela k + 1 entradas<br/>só de aberturas: de 1 a k + 1"]
P["duas delas, de profundidades i e j,<br/>com i menor que j, terminam no mesmo estado"]
C["acrescente i fechamentos às duas"]
D["só a de profundidade i fica balanceada,<br/>e a máquina dá a mesma resposta às duas"]
X["ela erra numa das duas"]
M["com mais estados, o argumento se refaz<br/>com o novo k: o obstáculo é ser finita"]
K --> E --> P --> C --> D --> X --> M
Conferir parênteses com a pilha
%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
I["comece com<br/>a pilha vazia"]
E{"a cadeia<br/>acabou?"}
Q{"leia o próximo<br/>símbolo: qual é?"}
A["abertura:<br/>empilhe uma marca"]
F{"fechamento:<br/>a pilha está vazia?"}
R1["recuse:<br/>o fechamento sobrou"]
D["desempilhe<br/>a marca do topo"]
V{"a pilha<br/>está vazia?"}
OK["aceite:<br/>balanceada"]
R2["recuse:<br/>sobrou abertura"]
I --> E
E -->|"não"| Q
Q -->|"("| A
Q -->|")"| F
F -->|"sim"| R1
F -->|"não"| D
A --> E
D --> E
E -->|"sim"| V
V -->|"sim"| OK
V -->|"não"| R2
(() sobra uma marca; em ()), o segundo fechamento encontra a pilha vazia.
Levar uma linha pelas seis fases
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
T["texto do programa"]
L["análise léxica"]
S["análise sintática"]
M["análise semântica"]
I["geração de código intermediário"]
O["otimização"]
F["geração de código final"]
R["código da máquina de destino"]
T --> L
L -->|"fluxo de símbolos"| S
S -->|"árvore da estrutura"| M
M -->|"árvore verificada<br/>+ tabela de nomes"| I
I -->|"representação intermediária"| O
O -->|"representação melhor<br/>pelo critério declarado"| F
F --> R
total = preco * quantidade vira cinco unidades, uma árvore, a árvore verificada com o nó paraReal, três operações, duas depois da otimização e cinco instruções.
Escrever a primeira especificação
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
D["(1) de que assunto a linguagem trata?<br/>é o domínio dela"]
A["(2) o que ela admite, e o que recusa?"]
F["(3) que forma tem o texto<br/>que alguém escreve nela?"]
P["(4) o que o sistema produz<br/>ao processar esse texto?"]
T{"dá para pôr a frase ao lado<br/>de um texto e dizer se ele passa?"}
RE["reescreva: a frase ainda não restringe nada"]
G["registre cada decisão com a alternativa<br/>descartada e o motivo"]
C["comece pelo menor recorte<br/>que ainda seja interessante"]
FP["guarde a gramática como saiu:<br/>a forma de partida"]
D --> A --> F --> P --> T
T -->|"não"| RE
RE --> A
T -->|"sim"| G --> C --> FP
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: Alfabeto e cadeia
Um alfabeto \Sigma é um conjunto finito e não vazio, cujos elementos são chamados símbolos. Uma cadeia sobre \Sigma é uma sequência finita a_1 a_2 \ldots a_n com a_i \in \Sigma para todo i, e n \geq 0. O número n é o comprimento da cadeia w = a_1 a_2 \ldots a_n, escrito |w|.
Definição: Linguagem
Uma linguagem L sobre um alfabeto \Sigma é um subconjunto de \Sigma^*, isto é, L \subseteq \Sigma^*. Nenhuma outra exigência é feita: L pode ser vazia, finita ou infinita, e não precisa ter regra, padrão ou descrição finita.
Definição: Operações sobre linguagens
Sejam L_1 e L_2 linguagens sobre \Sigma. A união é L_1 \cup L_2 = \{w : w \in L_1 \text{ ou } w \in L_2\}. A concatenação é L_1 L_2 = \{xy : x \in L_1 \text{ e } y \in L_2\}. A potência é L^0 = \{\varepsilon\} e L^{n+1} = L^n L. O fecho de Kleene é L^* = \bigcup_{n \geq 0} L^n.
Definição: Gramática
Uma gramática é uma quádrupla G = (V, \Sigma, P, S) em que V é um conjunto finito de não terminais, \Sigma é um alfabeto de terminais com V \cap \Sigma = \emptyset, P é um conjunto finito de produções da forma \alpha \to \beta com \alpha, \beta \in (V \cup \Sigma)^* e \alpha contendo ao menos um não terminal, e S \in V é o símbolo inicial.
Definição: Derivação e linguagem gerada
Escreve-se \gamma \alpha \delta \Rightarrow \gamma \beta \delta quando \alpha \to \beta é uma produção de G, e \Rightarrow^* para o fecho reflexivo e transitivo de \Rightarrow. A linguagem gerada por G é L(G) = \{ w \in \Sigma^* : S \Rightarrow^* w \}.
Definição: Árvore de derivação
Seja G = (V, \Sigma, P, S) uma gramática. Uma árvore é um conjunto finito de nós em que cada nó tem uma sequência ordenada de filhos e em que todo nó, exceto um — a raiz —, é filho de exatamente um outro nó; nó sem filhos chama-se folha, e a subárvore de um nó é esse nó com todos os seus descendentes. Uma árvore de derivação de G é uma árvore cuja raiz é rotulada com S, cujos nós internos são rotulados com elementos de V e cujas folhas são rotuladas com elementos de \Sigma ou com \varepsilon, e em que, para todo nó interno rotulado A cujos filhos são rotulados X_1, \ldots, X_n nessa ordem, A \to X_1 \cdots X_n é uma produção de P. A cadeia formada pelas folhas, lidas da esquerda para a direita, é a cadeia derivada pela árvore.
Alfabeto
Conjunto finito e não vazio de símbolos, a partir do qual se formam as cadeias de uma linguagem. Escreve-se \Sigma.
Análise léxica
Primeira fase do tradutor: recebe uma sequência de caracteres e devolve uma sequência de unidades classificadas, descartando espaços e comentários pelo caminho.
Análise semântica
Fase que verifica o que a forma do texto não garante — nome usado sem declaração, operação com operandos de tipo incompatível, violação das regras de escopo — e enriquece a árvore com as informações que a tradução para código consome.
Autômato de pilha
Máquina de estados finitos acrescida de uma pilha de memória auxiliar, cujas transições dependem do estado corrente, do símbolo lido e do símbolo no topo dessa memória. É o modelo que reconhece exatamente a família livre de contexto.
Cadeia
Sequência finita de símbolos de um alfabeto. Seu comprimento é o número de símbolos que a compõem, contando repetições.
Derivação
Sequência de substituições que parte do símbolo inicial de uma gramática e, a cada passo, troca um não terminal pelo corpo de uma de suas produções, até restarem apenas terminais.
Fecho de Kleene
Operação que forma, a partir de uma linguagem, o conjunto de todas as concatenações de zero ou mais cadeias dela. Inclui sempre a cadeia vazia.
Hierarquia de Chomsky
Classificação das linguagens em quatro classes encaixadas, obtida por restrição na forma das regras da gramática. A cada classe corresponde um tipo de máquina, e o que separa os tipos é a memória de que dispõem.
Item
Produção com uma posição marcada no corpo, escrita com um ponto. À esquerda do ponto está o que já foi reconhecido e se encontra na pilha; à direita, o que ainda se espera. Com o ponto no fim, indica que o corpo inteiro está na pilha.
Linguagem gerada
Conjunto das cadeias formadas só por terminais que se obtêm do símbolo inicial de uma gramática por alguma sequência de substituições.
Máquina virtual
Especificação de repertório de instruções, estado e semântica de execução realizada por um programa interpretador em vez de por circuito.
Não terminal
Símbolo de uma gramática que não aparece nas cadeias geradas e funciona como nome de uma construção da linguagem, a ser trocado pelo corpo de alguma de suas produções.
Produção
Regra de uma gramática que autoriza trocar uma cadeia de símbolos por outra. Na forma livre de contexto, o lado esquerdo é um único não terminal, chamado cabeça, e o direito é o corpo.
Recursão à esquerda
Propriedade de um não terminal que produz, em um ou mais passos, uma cadeia começada por ele mesmo. Faz laçar indefinidamente o analisador descendente, e remove-se reescrevendo as produções sem alterar a linguagem gerada.
Representação intermediária
Linguagem interposta entre a fonte e o alvo, com uma tradução de cada fonte para ela e uma dela para cada alvo. Com M fontes e N alvos, custa M + N traduções, contra M \times N na tradução direta.
Símbolo inicial
Não terminal a partir do qual começa toda derivação de uma gramática, e que nomeia a construção mais externa da linguagem.
Temporário
Nome criado pelo tradutor, sem correspondente no texto de origem, para guardar um resultado parcial da desmontagem de uma expressão composta.
Terminal
Símbolo de uma gramática que aparece nas cadeias geradas e não pode ser trocado por nada. No tradutor, corresponde às categorias que a fase de símbolos produz.
Token
Par formado pela categoria — o nome do padrão que reconheceu o lexema — e pelos atributos de que a fase seguinte precisa, tipicamente o próprio lexema, a posição de origem e, para nomes, a entrada correspondente na tabela de símbolos.
Compilador
Programa que traduz um texto escrito numa linguagem para outra preservando o significado. Organiza-se como encadeamento de programas pequenos, cada um de responsabilidade estreita, ligados por artefatos intermediários bem definidos.
Gramática livre de contexto
Gramática em que toda produção tem um único não terminal do lado esquerdo, podendo o lado direito ser qualquer sequência de terminais e não terminais. A substituição não depende do que cerca o símbolo — daí o nome.
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.
Mapa mental
Os tópicos do módulo, do centro para fora, na ordem do livro.
Painel do conhecimento
Conceitos
- Alfabeto, \Sigma: um conjunto finito e não vazio de símbolos. Cadeia: uma sequência finita deles, de comprimento |w|.
- Linguagem: um subconjunto de \Sigma^*, sem outra exigência.
- Operações sobre linguagens: união, concatenação, potência, com L^0 = \{\varepsilon\}, e fecho de Kleene.
- Gramática, G = (V, \Sigma, P, S), e a linguagem gerada L(G); a árvore de derivação dá a cadeia nas folhas.
- Hierarquia de Chomsky: quatro classes, ordenadas pela memória da máquina que as reconhece.
- Fase: uma tarefa do tradutor, que entrega à seguinte o que produziu.
Exemplos
total = preco * quantidade: 26 caracteres e cinco unidades, nas colunas 1, 7, 9, 15 e 17.3x: a decisão tomada no3que oxderruba.- L_1 = \{a, ab\} e L_2 = \{b, \varepsilon\}: L_1 L_2 = \{a, ab, abb\}, três cadeias de quatro pares.
(a+a): seis trocas, e uma árvore de onze nós.- Parênteses balanceados: fora do degrau regular.
- Com
preco2,5 equantidade4,totalpassa a valer 10,0.
Diagrama
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
subgraph T0["tipo 0 — irrestrita · máquina de Turing"]
subgraph T1["tipo 1 — sensível ao contexto · autômato linearmente limitado"]
subgraph T2["tipo 2 — livre de contexto · autômato de pilha"]
T3["tipo 3 — regular · autômato finito"]
end
end
end
Evidências
- 1952, num encontro da ACM: Grace Hopper apresenta The Education of a Computer, sobre o A-0, que rodava num UNIVAC I e montava um programa a partir de rotinas gravadas em fita.
- 1956: Noam Chomsky, linguista, publica Three Models for the Description of Language. O alvo era a língua natural, e não compiladores.
- 1957: a equipe de John Backus, na IBM, entrega o compilador de FORTRAN, sob a suspeita de que código gerado por máquina seria lento demais. A otimização foi condição de aceitação.
- Agosto de 1960, Mathematisch Centrum, Amsterdã: Edsger W. Dijkstra e Jaap A. Zonneveld concluem o primeiro compilador de ALGOL 60.
- Agosto de 1984: Ken Thompson publica nas Communications of the ACM o texto da palestra do Prêmio Turing, sobre a confiança em quem escreve o software. São trinta e dois anos depois de 1952.
Referências
- Hopper, The Education of a Computer, ACM, 1952.
- Chomsky, Three Models for the Description of Language, IRE Transactions on Information Theory, 1956.
- Backus, The History of FORTRAN I, II, and III, ACM SIGPLAN Notices, 1978.
- Naur (ed.), Report on the Algorithmic Language ALGOL 60, Communications of the ACM, v. 3, n. 5, 1960.
- Dijkstra, Recursive Programming, Numerische Mathematik, 1960.
- Thompson, Reflections on Trusting Trust, Communications of the ACM, ago. 1984.
- Bibliografia básica: Louden (Cengage, 2004), Barbosa (SAGAH, 2021), Neto (LTC, 1987).
Aplicações
- As palavras reservadas, como
ifewhile, formam uma linguagem finita, que se guarda por extenso. - A mensagem de erro sai durante a análise, enquanto há a posição do trecho: a linha e a coluna.
- A pilha volta em três lugares: no autômato de pilha, nas chamadas de um analisador escrito com funções que se chamam e nos registros de ativação.
- Nos módulos seguintes: o autômato finito, definido, no 03; o limite do reconhecimento regular, demonstrado, no 06; a forma de partida transformada no 08; a pilha como máquina no 09; a árvore de derivação construída por programa no 10.
Mapa conceitual
DicaAntes de olhar
Escreva num papel: alfabeto, símbolo, cadeia, cadeia vazia, universo, linguagem, fecho de Kleene, gramática, árvore de derivação, máquina, hierarquia de Chomsky, autômato finito, pilha, parênteses balanceados, tradutor, fase, fluxo de símbolos. Ligue os conceitos com setas, e escreva em cada seta um verbo que diga qual é a relação. Depois compare com o mapa.
Folha de consulta
Notação e leitura
- \Sigma: o alfabeto · |w|: o comprimento de w
- \varepsilon: a cadeia vazia, |\varepsilon| = 0, e \varepsilon \notin \Sigma
- \emptyset: o conjunto vazio · \Sigma^*: o universo, todas as cadeias sobre \Sigma
- L \subseteq \Sigma^*: “L está contido em sigma estrela”
- \Rightarrow: deriva em um passo · \Rightarrow^*: em zero ou mais passos
As operações, caso a caso
- cadeias: wv cola v no fim de w, e |wv| = |w| + |v|; a ordem muda o resultado, o agrupamento não; w^0 não tem símbolo
- L_1 \cup L_2: as cadeias que estão em L_1 ou em L_2
- L_1 L_2: cada cadeia de L_1 seguida de cada cadeia de L_2
- L^0 = \{\varepsilon\} e L^{n+1} = L^n L
- L^* = \bigcup_{n \geq 0} L^n: todas as potências, sem última
Contas
- o andar n de \{a, b\}^* tem 2^n cadeias; até o andar 3, são 15
- |\emptyset| = 0 e |\{\varepsilon\}| = 1
- |L_1 L_2| \leq |L_1| \cdot |L_2|: com \{a, ab\} e \{b, \varepsilon\}, quatro pares e três cadeias
- fecho de \{a, b\} com teto 3: 1 + 2 + 4 + 8 = 15 cadeias
- árvore de
(a+a): 11 nós, seis internos e cinco folhas - sem a tabela de nomes, 200 linhas pedem 200 \times 200 = 40.000 linhas lidas
Gramática e notação
- G = (V, \Sigma, P, S): não terminais, terminais, produções e símbolo inicial
- a produção recursiva traz o infinito:
E → E + TeT → ( E ) - árvore de derivação: raiz S, nós internos com não terminais, folhas com terminais ou \varepsilon
- na BNF, a barra se lê “ou” e o asterisco “zero ou mais vezes”
decl → item*desfaz-se emdecl → εedecl → item decl
A hierarquia
| Tipo | Classe | Máquina | Memória |
|---|---|---|---|
| 3 | regular | autômato finito | só o estado |
| 2 | livre de contexto | autômato de pilha | o estado e uma pilha |
| 1 | sensível ao contexto | autômato linearmente limitado | fita do tamanho da entrada |
| 0 | irrestrita | máquina de Turing | fita sem limite |
As seis fases
| Fase | Devolve à seguinte |
|---|---|
| análise léxica | o fluxo de símbolos |
| análise sintática | a árvore da estrutura |
| análise semântica | a árvore verificada e a tabela de nomes |
| código intermediário | a representação intermediária |
| otimização | outra representação, melhor por um critério declarado |
| código final | o código da máquina de destino |
Três estratégias
| Estratégia | Presente enquanto o programa roda |
|---|---|
| compilar | só o código da máquina de destino |
| híbrida | a forma intermediária e a máquina virtual |
| interpretar | o texto, ou a estrutura tirada dele, e o interpretador |
Erros previsíveis
- “L^0 = \emptyset” ou “L^0 = L”: L^0 = \{\varepsilon\}, e o acumulador que começa em \emptyset sai vazio para toda linguagem
- “\emptyset e \varepsilon são a mesma coisa”: um conjunto tem zero elementos, o outro tem um
- “a união tem as cadeias que estão nas duas”: isso é a interseção; a união diz ou
- “a concatenação tem exatamente |L_1| \cdot |L_2| cadeias”: tem no máximo isso, por causa das colisões
- “toda linguagem tem descrição finita”, ou “ainda não a descobriram”: quase nenhuma tem, e isso está demonstrado
- “com mais estados, a máquina finita reconhece os balanceados”: o obstáculo é ser finita, e não ser pequena
- “o que separa os degraus é o alfabeto, o número de regras ou a velocidade”: é a memória, e o acesso a ela
- “a linguagem que um padrão denota é o texto do padrão”: o texto pede pilha; o conjunto denotado é regular
- “o tradutor sabe que você queria
x3”: ele sabe só que o texto não pertence - “traduzir e rodar são o mesmo”: a tradução não multiplicou nada; os valores só chegam na execução