Autômatos e Linguagens Formais

Autômatos e Linguagens Formais: Fundamentos Teóricos dos Compiladores
Uma jornada pelos conceitos teóricos que fundamentam a construção de compiladores. Aprenda sobre autômatos, gramáticas e linguagens formais, elementos essenciais para entender como um compilador analisa e processa código-fonte.
Por que Estudar Autômatos em Compiladores?
Autômatos são máquinas abstratas que servem como modelos matemáticos para computação. No contexto de compiladores, eles desempenham um papel fundamental:
Fornecem uma base teórica sólida para análise léxica e sintática
Permitem reconhecer padrões em códigos-fonte
Estabelecem limites do que pode ser analisado
São implementados diretamente em geradores de analisadores
Cada fase de um compilador utiliza algum tipo de autômato ou gramática para transformar código-fonte em código-objeto executável.
Onde os Autômatos Aparecem no Processo de Compilação?
Análise Léxica
Autômatos Finitos (AF) são utilizados para reconhecer tokens no código-fonte, como identificadores, números e palavras-chave.
Análise Sintática
Autômatos com Pilha (AP) e algoritmos baseados em gramáticas livres de contexto verificam se a estrutura do programa está correta.
Geração de Código
Autômatos podem ser usados para reconhecer padrões no código intermediário e gerar código otimizado.
Compreender a teoria dos autômatos permite desenvolver compiladores mais eficientes e robustos, capazes de identificar e tratar corretamente as construções das linguagens de programação.
Visão Geral: Linguagem, Gramática e Máquina
Existe uma relação estreita entre estes três conceitos fundamentais:
Linguagem Formal
Conjunto de cadeias formadas por símbolos de um alfabeto, seguindo regras específicas. É o que queremos reconhecer ou gerar.
Gramática
Conjunto de regras que define como as cadeias válidas da linguagem podem ser construídas. É um mecanismo gerador.
Máquina/Autômato
Dispositivo abstrato que reconhece se uma cadeia pertence ou não a uma linguagem. É um mecanismo reconhecedor.
Cada tipo de linguagem formal tem uma classe correspondente de gramáticas e máquinas capazes de gerá-la ou reconhecê-la.
Definição de Linguagem Formal
Uma linguagem formal é um conjunto (possivelmente infinito) de cadeias de comprimento finito, formadas a partir de um alfabeto finito.
Em termos matemáticos, se Σ é um alfabeto (conjunto finito de símbolos), então:
Σ* representa o conjunto de todas as cadeias possíveis sobre Σ
Uma linguagem L sobre Σ é um subconjunto de Σ* (ou seja, L ⊆ Σ*)
Por exemplo, se Σ = {a, b}, algumas linguagens possíveis são:
L₁ = {a, aa, aaa, ...} = {aⁿ | n > 0}
L₂ = {ab, aabb, aaabbb, ...} = {aⁿbⁿ | n > 0}
L₃ = {ε, a, b, aa, ab, ba, bb, ...} = Σ* (todas as cadeias)
Cada uma dessas linguagens requer diferentes mecanismos para reconhecimento.
Alfabeto, Cadeia e Linguagem
Alfabeto (Σ)
Conjunto finito e não vazio de símbolos. Por exemplo:
Σ = {0, 1} (alfabeto binário)
Σ = {a, b, c, ..., z} (alfabeto de letras minúsculas)
Σ = {if, else, while, ...} (palavras-chave de uma linguagem)
Cadeia (ou palavra)
Sequência finita de símbolos de um alfabeto.
Exemplos sobre Σ = {a, b}: a, ab, bba, ababba
ε representa a cadeia vazia (sem símbolos)
|w| denota o comprimento da cadeia w
Linguagem
Conjunto de cadeias formadas pelos símbolos do alfabeto. Pode ser:
Finita: L = {a, ab, abb}
Infinita: L = {aⁿ | n ≥ 0}
Vazia: L = ∅
Hierarquia de Chomsky
Noam Chomsky classificou as linguagens formais e suas gramáticas em quatro níveis hierárquicos, cada um com poder expressivo diferente:
1
2
3
4
1
Tipo 0
Linguagens Recursivamente Enumeráveis
2
Tipo 1
Linguagens Sensíveis ao Contexto
3
Tipo 2
Linguagens Livres de Contexto
4
Tipo 3
Linguagens Regulares
Cada tipo é um subconjunto do tipo anterior, ou seja, toda linguagem regular é também livre de contexto, que por sua vez é sensível ao contexto, e assim por diante.
Linguagens Regulares vs. Linguagens Livres de Contexto
Linguagens Regulares (Tipo 3)
Reconhecidas por autômatos finitos
Definidas por expressões regulares
Usadas na análise léxica (reconhecimento de tokens)
Não podem expressar aninhamento arbitrário
Exemplo: identificadores, números, etc.
Linguagens Livres de Contexto (Tipo 2)
Reconhecidas por autômatos com pilha
Definidas por gramáticas livres de contexto
Usadas na análise sintática
Podem expressar aninhamento balanceado
Exemplo: expressões aritméticas, declarações aninhadas
Na prática, a maioria das linguagens de programação tem sua sintaxe definida por gramáticas livres de contexto, enquanto os tokens individuais são descritos por expressões regulares.
Exemplos: Linguagem Regular vs. Não Regular
1
Linguagens Regulares
L₁ = {cadeiras que terminam com 'ab'}
L₂ = {cadeiras com número par de 'a's}
L₃ = {identificadores que começam com letra}
L₄ = {comentários de linha única}
L₅ = todas as cadeias sem 'abc'
2
Linguagens Não Regulares
L₁ = {aⁿbⁿ | n ≥ 0} (mesmo número de a's e b's)
L₂ = {a^n b^m c^n | n,m ≥ 0} (número igual de a's e c's)
L₃ = {expressões aritméticas bem formadas}
L₄ = {programas com blocos balanceados}
L₅ = {strings palíndromas}
A principal limitação das linguagens regulares é não conseguirem "contar" ou manter um histórico arbitrário, o que é necessário para reconhecer construções aninhadas ou balanceadas.
Definição de Autômato Finito Determinístico (AFD)
Um Autômato Finito Determinístico é formalmente definido como uma quíntupla:
M = (Q, \Sigma, \delta, q_0, F)Onde:
Q
Conjunto finito de estados
Σ
Alfabeto de entrada
δ
Função de transição: Q × Σ → Q
q₀
Estado inicial (q₀ ∈ Q)
F
Conjunto de estados finais (F ⊆ Q)
"Determinístico" significa que, para cada estado e símbolo de entrada, existe exatamente uma transição possível. AFDs são amplamente utilizados em compiladores para implementar a análise léxica.
Transições, Estados e Funcionamento de um AFD
O funcionamento de um AFD segue estes princípios:
Começa no estado inicial q₀
Lê um símbolo da entrada
Muda para o estado indicado pela função de transição
Repete até processar toda a entrada
Se terminar em um estado final, a cadeia é aceita; caso contrário, é rejeitada
Uma cadeia é reconhecida (ou aceita) pelo autômato se, após ler todos os símbolos da cadeia, o autômato estiver em um estado final.
A linguagem reconhecida por um AFD é o conjunto de todas as cadeias que ele aceita.
Exemplo Prático: Reconhecendo Strings com "ab"
Vamos construir um AFD que reconhece todas as cadeias sobre o alfabeto Σ = {a, b} que contêm a subcadeia "ab".
O autômato possui 3 estados:
q₀: Estado inicial (ainda não vimos 'a')
q₁: Vimos um 'a' e estamos esperando um 'b'
q₂: Estado final (encontramos "ab")
A função de transição é:
δ(q₀, a) = q₁ (se lermos 'a' no estado inicial, vamos para q₁)
δ(q₀, b) = q₀ (se lermos 'b' no estado inicial, permanecemos em q₀)
δ(q₁, a) = q₁ (se lermos 'a' em q₁, permanecemos em q₁)
δ(q₁, b) = q₂ (se lermos 'b' em q₁, vamos para o estado final q₂)
δ(q₂, a) = q₁ (se lermos 'a' no estado final, voltamos para q₁)
δ(q₂, b) = q₂ (se lermos 'b' no estado final, permanecemos em q₂)
Autômato Finito Não Determinístico (AFN)
Um Autômato Finito Não Determinístico (AFN) é similar ao AFD, mas com duas diferenças fundamentais:
Para um estado e símbolo, pode haver múltiplas transições possíveis (ou nenhuma)
Permite transições ε (epsilon), que não consomem símbolos de entrada
Formalmente, um AFN é uma quíntupla M = (Q, Σ, δ, q₀, F), onde δ: Q × (Σ ∪ {ε}) → P(Q) mapeia para o conjunto potência dos estados.
Uma cadeia é aceita se existe pelo menos um caminho do estado inicial a algum estado final processando a cadeia completa.
AFNs não são mais poderosos que AFDs em termos de linguagens reconhecidas, mas podem ser mais compactos e intuitivos para projetar.
Equivalência entre AFD e AFN
Todo AFN pode ser convertido em um AFD equivalente que reconhece a mesma linguagem. Este processo é conhecido como "construção do conjunto de potência" ou "algoritmo de subconjuntos".
1
AFN Original
Cada estado do AFN pode ter múltiplas transições para o mesmo símbolo ou transições ε.
2
Construção do Conjunto de Potência
Cada estado do novo AFD corresponde a um subconjunto de estados do AFN. Calculamos o "fecho-ε" e as transições para cada símbolo.
3
AFD Resultante
O AFD terá no máximo 2^n estados, onde n é o número de estados do AFN original.
Na prática, muitos geradores de analisadores léxicos, como o Flex, permitem que você especifique padrões usando construções não determinísticas, mas geram implementações determinísticas para eficiência.
Limitações dos Autômatos Finitos
Os autômatos finitos são poderosos, mas têm limitações importantes para compiladores.
Sem Memória
AFDs e AFNs não possuem memória além do estado atual, não podendo "contar" eventos passados indefinidamente.
Aninhamento
Não conseguem reconhecer construções aninhadas arbitrariamente, como parênteses balanceados ou blocos de código.
Recursividade
Não podem lidar com definições recursivas, comuns em linguagens de programação (como expressões dentro de expressões).
Para superar essas limitações na análise sintática, precisamos de um modelo computacional mais poderoso: o Autômato com Pilha.
Introdução ao Autômato com Pilha
Um Autômato com Pilha (AP) é uma extensão do autômato finito que adiciona uma estrutura de dados do tipo pilha, permitindo "memória" potencialmente ilimitada.
Formalmente, um AP é uma sétupla M = (Q, Σ, Γ, δ, q₀, Z₀, F), onde:
Q: conjunto finito de estados
Σ: alfabeto de entrada
Γ: alfabeto da pilha
δ: função de transição
q₀: estado inicial
Z₀: símbolo inicial da pilha
F: conjunto de estados finais
A função de transição considera não apenas o estado atual e o símbolo de entrada, mas também o símbolo no topo da pilha.
Componentes do Autômato com Pilha
Estados
Conjunto finito de estados de controle, como nos autômatos finitos.
Pilha
Estrutura de dados LIFO (Last In, First Out) que permite armazenar informações sobre o contexto da análise.
Transições
Definidas pela função δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)
Em cada transição, o AP pode:
Ler um símbolo da entrada (ou não, no caso de ε-transições)
Retirar o símbolo do topo da pilha
Mudar de estado
Empilhar zero ou mais símbolos
A pilha fornece a capacidade de "contar" e "lembrar" necessária para reconhecer linguagens livres de contexto.
Exemplo: Linguagem aⁿbⁿ
Vamos construir um autômato com pilha para reconhecer a linguagem L = {aⁿbⁿ | n ≥ 1}, que não é regular.
A estratégia é:
Para cada 'a' lido, empilhamos um símbolo na pilha
Para cada 'b' lido, desempilhamos um símbolo
Se terminarmos com a pilha vazia após ler toda a entrada, a cadeia é aceita
O autômato inicia com um símbolo especial Z₀ na pilha. Quando lê 'a', empilha 'A'. Quando lê 'b', verifica se há 'A' no topo da pilha e o remove. Se a entrada termina e só resta Z₀ na pilha, a cadeia é aceita.
Este exemplo demonstra a capacidade do AP de "contar" as ocorrências de 'a' e compará-las com as de 'b', algo impossível para autômatos finitos.
Ligação entre Autômatos com Pilha e Gramáticas Livres de Contexto
Existe uma correspondência fundamental entre autômatos com pilha e gramáticas livres de contexto:
Uma linguagem é reconhecida por um AP se e somente se pode ser gerada por uma GLC
Os estados do AP correspondem a configurações da análise sintática
A pilha armazena símbolos não terminais pendentes
As transições implementam as regras de produção da gramática
Na prática, analisadores sintáticos como os de tipo LL ou LR são implementações especializadas de autômatos com pilha que processam a entrada de acordo com uma gramática livre de contexto.
Gramáticas Regulares (Revisão)
As gramáticas regulares correspondem às linguagens regulares (Tipo 3) na hierarquia de Chomsky.
Formato das Produções
As produções têm uma das formas:
A → aB (linear à direita)
A → a
A → ε
Onde A, B são não terminais, e a é um terminal.
Equivalência com AFs
Gramáticas regulares são equivalentes em poder expressivo aos autômatos finitos. Para cada gramática regular, existe um AFN equivalente, e vice-versa.
Uso em Compiladores
Usadas principalmente para definir os tokens (lexemas) da linguagem. Cada token pode ser descrito por uma expressão regular, que é equivalente a uma gramática regular.
Embora mais limitadas que as gramáticas livres de contexto, as gramáticas regulares são suficientes para a análise léxica e muito mais simples de processar.
Gramáticas Livres de Contexto (GLC)
As gramáticas livres de contexto correspondem às linguagens de Tipo 2 na hierarquia de Chomsky.
Definição Formal
Uma GLC é uma quádrupla G = (V, T, P, S), onde:
V: conjunto de símbolos não terminais
T: conjunto de símbolos terminais
P: conjunto de regras de produção da forma A → α, onde A ∈ V e α ∈ (V ∪ T)*
S: símbolo inicial (S ∈ V)
Características
O lado esquerdo de cada produção contém exatamente um não terminal
O lado direito pode conter qualquer sequência de terminais e não terminais
A substituição ocorre independentemente do contexto
Permite definições recursivas
As GLCs são fundamentais na definição da sintaxe de linguagens de programação, permitindo expressar construções aninhadas como expressões, blocos e estruturas de controle.
Regras de Produção e Derivação
As regras de produção definem como os símbolos não terminais podem ser expandidos ou substituídos durante o processo de derivação.
Formato das Regras
A → α, onde A é um não terminal e α é uma sequência de terminais e não terminais.
Exemplos:
S → aAb
A → aA | ε
expr → expr + term | term
Derivação
Processo de aplicar regras de produção sequencialmente para transformar o símbolo inicial em uma cadeia de terminais.
Notação: α ⇒ β (α deriva β em um passo)
α ⇒* β (α deriva β em zero ou mais passos)
A linguagem gerada por uma gramática G é o conjunto de todas as cadeias de terminais que podem ser derivadas a partir do símbolo inicial S.
L(G) = {w ∈ T* | S ⇒* w}
Árvores de Derivação e Sentenças Válidas
Uma árvore de derivação (ou árvore sintática) é uma representação gráfica de como uma sentença é derivada em uma gramática livre de contexto.
Estrutura
A raiz é o símbolo inicial da gramática
Os nós internos são símbolos não terminais
As folhas são símbolos terminais ou ε
Cada nó com seus filhos representa uma aplicação de uma regra de produção
Sentenças Válidas
Uma sentença é válida na linguagem se existe uma árvore de derivação cuja sequência de folhas (lidas da esquerda para direita) é exatamente a sentença.
Ambiguidade
Uma gramática é ambígua se existe alguma sentença que pode ser representada por mais de uma árvore de derivação. Ambiguidade é geralmente indesejável em linguagens de programação.
Comparação Visual entre AFD, AP e GLC
1
Autômato Finito (AFD)
Reconhece linguagens regulares (Tipo 3)
Memória limitada aos estados
Implementação eficiente (matriz de transição)
Usado na análise léxica (scanner)
2
Autômato com Pilha (AP)
Reconhece linguagens livres de contexto (Tipo 2)
Memória expandida com pilha
Implementação mais complexa
Base para analisadores sintáticos
3
Gramática Livre de Contexto (GLC)
Gera linguagens livres de contexto (Tipo 2)
Naturalmente recursiva
Formalismo declarativo
Especifica a sintaxe da linguagem
Estas três estruturas são fundamentais na teoria e implementação de compiladores, cada uma atendendo a diferentes aspectos do processo de compilação.
Ferramentas Recomendadas para Simulação
JFLAP
Uma ferramenta gráfica interativa para criação e simulação de autômatos finitos, autômatos com pilha e gramáticas.
Interface visual para desenhar autômatos
Simulação passo a passo
Conversão entre diferentes formalismos
Multiplataforma (Java)
Outras Ferramentas
Visual Automata Simulator: Alternativa mais leve ao JFLAP
FAdo (Python): Biblioteca para manipulação formal de autômatos
Simuladores online: Várias opções para uso sem instalação
Estas ferramentas permitem visualizar e entender o comportamento dos autômatos, tornando mais concretos os conceitos teóricos discutidos.
Simulação de um AFD: Reconhecendo "(a|b)abb"
Vamos projetar e simular um AFD que reconhece cadeias sobre {a, b} que terminam com a subcadeia "abb".
O autômato possui os seguintes estados:
q₀: Estado inicial
q₁: Vimos um 'a' (início potencial de "abb")
q₂: Vimos "ab"
q₃: Vimos "abb" (estado final)
A função de transição δ define todas as possíveis transições entre estados. Por exemplo:
δ(q₀, a) = q₁ (se lemos 'a' no estado q₀, vamos para q₁)
δ(q₁, b) = q₂ (se lemos 'b' no estado q₁, vamos para q₂)
δ(q₂, b) = q₃ (se lemos 'b' no estado q₂, vamos para q₃)
No JFLAP, podemos testar cadeias como "abb", "aabb", "bababb" (aceitas) e "ab", "ba", "abba" (rejeitadas).
Construindo e Testando um AP para aⁿbⁿ
Vamos implementar no JFLAP um autômato com pilha para reconhecer a linguagem L = {aⁿbⁿ | n ≥ 1}.
O algoritmo para reconhecer aⁿbⁿ funciona assim:
Iniciar com um símbolo Z₀ na pilha e no estado q₀
Para cada 'a' lido na entrada, empilhar um símbolo A
Ao ler o primeiro 'b', mudar para um estado q₁
Para cada 'b' subsequente, desempilhar um símbolo A
Se a entrada terminar, a pilha estiver vazia (exceto por Z₀) e estivermos no estado q₁, aceitar
Podemos testar cadeias como "ab", "aabb", "aaabbb" (aceitas) e "aab", "abb", "ba" (rejeitadas).
Exercício: Desenhe e Teste um AFD no JFLAP
Exercício prático para implementar no JFLAP:
Construa um AFD que reconheça todas as cadeias sobre o alfabeto Σ = {a, b} que possuem um número par de 'a's e um número ímpar de 'b's.
Dicas para a solução:
Você precisará de 4 estados para rastrear as combinações de paridade
Estados: (par-a, par-b), (par-a, ímpar-b), (ímpar-a, par-b), (ímpar-a, ímpar-b)
Apenas o estado (par-a, ímpar-b) será final
Cada transição muda a paridade do contador correspondente ao símbolo lido
Teste sua solução com cadeias como "ab", "aab", "bb", "aabb", "abab", etc.
Exercício: Verifique se uma String Pertence à GLC Dada
Considere a seguinte gramática livre de contexto:
S → aSb | aAb
A → aA | ε
Exercício: Verifique se as seguintes cadeias pertencem à linguagem gerada por essa gramática:
aab
aaabb
aabbb
aaaabbb
Para cada cadeia, tente construir uma derivação a partir do símbolo inicial S. Se conseguir, a cadeia pertence à linguagem.
Por exemplo, para "aab":
S → aAb
A → ε
Resultado: aεb = aab
Portanto, "aab" pertence à linguagem.
Resumo e Próximos Passos
Linguagens Formais
Fundamento matemático para descrever conjuntos de cadeias válidas, organizadas na hierarquia de Chomsky.
Autômatos Finitos
Modelos computacionais que reconhecem linguagens regulares, fundamentais para análise léxica.
Autômatos com Pilha
Extensão dos autômatos finitos com uma pilha, capazes de reconhecer linguagens livres de contexto.
Gramáticas
Sistemas formais para gerar linguagens, usados para definir a sintaxe de linguagens de programação.
Próxima Aula: Expressões Regulares e Lexers
Vamos aprofundar o estudo da análise léxica, explorando como expressões regulares são utilizadas para definir tokens e como implementar analisadores léxicos eficientes.