flowchart TD
A[🤖 AFDs<br/>Semana 5] --> B[🌊 AFNs<br/>Semana 6]
B --> C[⚖️ Propriedades<br/>Semana 7]
B --> D[🔬 Análise Léxica<br/>Semana 8]
B --> E[🛠️ Projeto Integrador<br/>Design Elegante de Autômatos]
E --> F[📐 Construção de AFNs]
E --> G[🔄 Conversão AFN→AFD]
E --> H[💻 Integração no Analisador]
style A fill:#e3f2fd
style B fill:#e8f5e8
style C fill:#fff3e0
style D fill:#f3e5f5
Autômatos Finitos Não-Determinísticos: Explorando o Poder da Escolha Múltipla
🌊
Bem-vindo ao sexto tema da nossa jornada! Hoje você mergulhará no fascinante universo dos autômatos finitos não-determinísticos, descobrindo como o conceito de “múltiplas escolhas simultâneas” revoluciona o design de algoritmos e oferece perspectivas elegantes para problemas computacionais complexos.
Imagine um labirinto onde, em cada bifurcação, você pode seguir todos os caminhos simultaneamente, explorando múltiplas possibilidades em paralelo até encontrar a saída. Esta é a essência do não-determinismo computacional! Enquanto na semana passada estudamos autômatos que sempre sabem exatamente qual decisão tomar (AFDs), hoje descobriremos máquinas que podem “adivinhar” o caminho certo, tomando múltiplas decisões ao mesmo tempo. Embora este conceito possa parecer fantástico, ele oferece ferramentas conceituais poderosas que simplificam drasticamente o design de algoritmos para reconhecimento de padrões.
🎯 Desvendando a Natureza do Não-Determinismo
O conceito de não-determinismo em computação representa uma das ideias mais fascinantes e contraintuitivas que você encontrará na teoria da computação. Diferente do mundo físico, onde cada evento tem uma causa determinística, no universo matemático podemos conceber máquinas que, diante da mesma situação, podem reagir de múltiplas formas diferentes simultaneamente.
Quando você encontra um autômato finito não-determinístico pela primeira vez, é natural experimentar uma sensação de estranhamento. Como uma máquina pode estar em múltiplos estados ao mesmo tempo? Como pode seguir várias transições simultaneamente? Esta sensação é completamente normal e, na verdade, indica que você está começando a expandir sua intuição computacional para além dos limites do pensamento sequencial tradicional.
O não-determinismo não é caos nem aleatoriedade. É uma forma estruturada e matematicamente rigorosa de expressar múltiplas possibilidades de processamento. Pense nele como uma ferramenta conceitual que nos permite descrever algoritmos de forma mais natural e elegante, mesmo sabendo que a implementação final será sempre determinística.
💡 Intuição Fundamental do Não-Determinismo
Um autômato finito não-determinístico é como um explorador muito otimista que, diante de múltiplos caminhos em uma floresta, magicamente se clona para explorar todos os caminhos simultaneamente. Se qualquer um dos clones encontra o destino desejado, a missão é considerada bem-sucedida.
Esta capacidade de “estar em múltiplos lugares ao mesmo tempo” permite que AFNs expressem padrões complexos de forma surpreendentemente simples e natural, frequentemente resultando em especificações muito mais compactas que suas contrapartes determinísticas.
A beleza conceitual dos AFNs reside na sua capacidade de separar a lógica de reconhecimento de padrões das preocupações de implementação eficiente. Quando você projeta um AFN, pode focar exclusivamente na expressão clara e elegante do padrão que deseja reconhecer, sem se preocupar com questões de eficiência computacional que serão resolvidas posteriormente durante a conversão para AFD.
O paradoxo aparente é que AFNs, apesar de sua flexibilidade conceitual, não são mais poderosos que AFDs em termos de quais linguagens podem reconhecer. Esta equivalência fundamental - uma das descobertas mais surpreendentes da teoria da computação - significa que o não-determinismo oferece conveniência de design sem comprometer limitações teóricas.
A aplicação prática desta equivalência é transformadora: você pode usar AFNs como ferramenta de design e prototipagem, aproveitando sua elegância conceitual, e depois converter automaticamente para AFDs para implementação eficiente. Esta abordagem combina o melhor dos dois mundos: clareza de especificação com performance de execução.
📐 Definição Formal e Estrutura dos AFNs
Para compreender verdadeiramente os autômatos finitos não-determinísticos, precisamos estabelecer suas fundações matemáticas com precisão rigorosa. A definição formal de um AFN estende a estrutura dos AFDs de forma cuidadosa, introduzindo não-determinismo de maneira controlada e matematicamente elegante.
🔬 Definição Formal de AFN
Um autômato finito não-determinístico é uma quíntupla M = (Q, \Sigma, \delta, q_0, F) onde:
- Q é um conjunto finito de estados
- \Sigma é o alfabeto de entrada (conjunto finito de símbolos)
- \delta: Q \times \Sigma \rightarrow \mathcal{P}(Q) é a função de transição que mapeia um estado e um símbolo para um conjunto de estados possíveis
- q_0 \in Q é o estado inicial
- F \subseteq Q é o conjunto de estados finais (ou de aceitação)
A diferença fundamental para AFDs está na função de transição: enquanto \delta em um AFD retorna um único estado, em um AFN retorna um conjunto de estados (possivelmente vazio).
Esta mudança aparentemente pequena na definição da função de transição tem consequências profundas. O fato de \delta retornar um conjunto de estados significa que, a partir de um estado específico ao ler um símbolo particular, o autômato pode “escolher” qualquer dos estados no conjunto retornado. Esta escolha não é aleatória - o autômato explora todas as possibilidades simultaneamente.
A notação \mathcal{P}(Q) representa o conjunto potência de Q, ou seja, o conjunto de todos os subconjuntos possíveis de Q. Esta notação captura precisamente a natureza do não-determinismo: para cada par (estado, símbolo), a função de transição pode retornar qualquer subconjunto dos estados disponíveis, incluindo o conjunto vazio (indicando que não há transições válidas) ou conjuntos com múltiplos elementos (indicando múltiplas escolhas possíveis).
As implicações práticas desta definição emergem quando consideramos como processar uma palavra de entrada. Ao contrário dos AFDs, onde o processamento segue um caminho único e bem definido, os AFNs seguem múltiplos caminhos simultaneamente. Em cada passo, o conjunto de estados ativos pode crescer, diminuir, ou até mesmo se tornar vazio.
Compreendendo a Dinâmica de Processamento
O processamento de uma palavra por um AFN requer uma perspectiva fundamentalmente diferente da que você desenvolveu para AFDs. Em vez de rastrear um único estado atual, você deve rastrear um conjunto de estados ativos que representa todas as possibilidades de processamento que permanecem viáveis.
⚙️ Algoritmo de Processamento em AFNs
Inicialização: O conjunto de estados ativos começa contendo apenas o estado inicial: \{q_0\}
Processamento de cada símbolo a: Para cada estado q no conjunto atual de estados ativos, aplicamos \delta(q, a) e formamos a união de todos os conjuntos resultantes.
Aceitação: A palavra é aceita se, após processar todos os símbolos, pelo menos um estado final está no conjunto de estados ativos.
Formalmente, se S_i representa o conjunto de estados ativos após processar os primeiros i símbolos da palavra w = a_1a_2...a_n, então:
- S_0 = \{q_0\}
- S_{i+1} = \bigcup_{q \in S_i} \delta(q, a_{i+1})
A palavra w é aceita se e somente se S_n \cap F \neq \emptyset.
Esta formulação matemática captura elegantemente a essência do não-determinismo: em cada passo, exploramos todas as possibilidades de transição a partir dos estados atualmente ativos, mantendo vivas todas as alternativas viáveis. O critério de aceitação reflete a natureza “otimista” dos AFNs - basta que uma das possibilidades de processamento termine em um estado de aceitação para que toda a computação seja considerada bem-sucedida.
A explosão combinatória é uma preocupação natural ao considerar este processo. Em princípio, o número de estados ativos pode crescer exponencialmente com o comprimento da palavra de entrada. No entanto, como o número total de estados é finito, o número de conjuntos de estados ativos possíveis também é limitado (especificamente, por 2^{|Q|}). Esta observação será fundamental quando estudarmos a conversão de AFNs para AFDs.
A simplicidade conceitual do algoritmo de processamento é uma das grandes virtudes dos AFNs. Não há decisões complexas a tomar ou heurísticas a aplicar - simplesmente seguimos todas as possibilidades em paralelo até que uma delas nos leve ao sucesso ou todas se esgotem sem encontrar aceitação.
🎨 Construindo AFNs: Técnicas e Estratégias
A construção de autômatos finitos não-determinísticos é uma arte que combina intuição matemática com insight prático. Diferente dos AFDs, onde cada transição deve ser cuidadosamente planejada para evitar caminhos sem saída, os AFNs permitem uma abordagem mais flexível e exploratória para o design.
Técnicas Fundamentais de Construção
Construção por decomposição: Uma das estratégias mais poderosas para construir AFNs é decompor o padrão desejado em subpadrões menores e mais gerenciáveis. Cada subpadrão pode ser implementado com seu próprio conjunto de estados, e o não-determinismo permite combinar estes componentes de forma elegante.
Por exemplo, se você quiser reconhecer palavras que contêm ‘ab’ ou terminam com ‘ba’, pode construir dois AFNs separados - um para cada condição - e depois combiná-los usando transições não-determinísticas que permitem explorar ambas as possibilidades simultaneamente.
Construção por antecipação: AFNs permitem que você “aposte” em padrões futuros de forma que seria impossível em AFDs sem informação prévia. Quando o autômato encontra um símbolo que pode ser o início de um padrão importante, ele pode criar uma ramificação não-determinística para seguir esta possibilidade enquanto continua o processamento normal.
Esta técnica é particularmente valiosa para padrões onde o contexto futuro determina a interpretação de símbolos atuais. O autômato pode manter múltiplas “hipóteses” sobre qual padrão está sendo processado, resolvendo a ambiguidade apenas quando informação suficiente se torna disponível.
Casos Reais de Aplicação das Técnicas de Construção
Para tornar as técnicas de construção mais tangíveis e práticas, vamos explorar casos reais onde AFNs são fundamentais para resolver problemas computacionais do mundo real. Estes exemplos demonstram como os conceitos teóricos que você está aprendendo se materializam em soluções elegantes para desafios práticos.
Caso Real 1: Validação de Endereços de Email 📧
Imagine que você está desenvolvendo um sistema de cadastro para uma plataforma de e-commerce. Um dos requisitos mais básicos, mas tecnicamente desafiadores, é validar se um endereço de email inserido pelo usuário está em um formato válido.
O Desafio Prático: Emails têm uma estrutura complexa definida pelo RFC 5322, mas mesmo uma versão simplificada envolve múltiplas partes opcionais: parte local (antes do @), domínio, subdomínios, e extensões. Construir um AFD diretamente para este padrão seria extremamente complexo.
Solução com AFN - Decomposição Modular:
graph TB
subgraph "AFN para Validação de Email"
A[Início] --> B[Parte Local]
B --> C["@"]
C --> D[Domínio]
D --> E[Ponto]
E --> F[Extensão]
F --> G[Fim]
subgraph "Subautômatos"
H[AFN Parte Local<br/>a-z, 0-9, ., _]
I[AFN Domínio<br/>a-z, 0-9, -]
J[AFN Extensão<br/>2-4 letras]
end
B -.-> H
D -.-> I
F -.-> J
end
style A fill:#e3f2fd
style G fill:#90EE90
style H fill:#fff3e0
style I fill:#fff3e0
style J fill:#fff3e0
Implementação Prática com Decomposição:
class ValidadorEmailAFN:
def __init__(self):
# Constrói AFN modular para validação de email
self.afn_parte_local = self._construir_parte_local()
self.afn_dominio = self._construir_dominio()
self.afn_extensao = self._construir_extensao()
def _construir_parte_local(self):
"""AFN para parte local: letras, números, pontos, underscores"""
estados = {'q0', 'q1', 'q2'}
transicoes = {
# Primeiro caractere deve ser letra ou número
('q0', 'letra'): {'q1'},
('q0', 'numero'): {'q1'},
# Caracteres subsequentes podem incluir . e _
('q1', 'letra'): {'q1'},
('q1', 'numero'): {'q1'},
('q1', '.'): {'q2'},
('q1', '_'): {'q2'},
# Após ponto ou underscore, deve vir letra ou número
('q2', 'letra'): {'q1'},
('q2', 'numero'): {'q1'},
}
return AFN(estados, {'letra', 'numero', '.', '_'},
transicoes, 'q0', {'q1'})
def _construir_dominio(self):
"""AFN para domínio: letras, números, hífens"""
estados = {'d0', 'd1', 'd2'}
transicoes = {
('d0', 'letra'): {'d1'},
('d0', 'numero'): {'d1'},
('d1', 'letra'): {'d1'},
('d1', 'numero'): {'d1'},
('d1', '-'): {'d2'},
('d2', 'letra'): {'d1'},
('d2', 'numero'): {'d1'},
}
return AFN(estados, {'letra', 'numero', '-'},
transicoes, 'd0', {'d1'})
def _construir_extensao(self):
"""AFN para extensão: 2-4 letras"""
estados = {'e0', 'e1', 'e2', 'e3', 'e4'}
transicoes = {
('e0', 'letra'): {'e1'},
('e1', 'letra'): {'e2'},
('e2', 'letra'): {'e3'},
('e3', 'letra'): {'e4'},
}
return AFN(estados, {'letra'}, transicoes, 'e0', {'e2', 'e3', 'e4'})
def validar_email(self, email):
"""Valida email usando AFNs modulares"""
try:
partes = email.split('@')
if len(partes) != 2:
return False, "Email deve conter exatamente um @"
parte_local, dominio_completo = partes
# Valida parte local
if not self._processar_parte_local(parte_local):
return False, "Parte local inválida"
# Separa domínio e extensão
partes_dominio = dominio_completo.split('.')
if len(partes_dominio) < 2:
return False, "Domínio deve conter pelo menos um ponto"
extensao = partes_dominio[-1]
dominio = '.'.join(partes_dominio[:-1])
# Valida domínio
if not self._processar_dominio(dominio):
return False, "Domínio inválido"
# Valida extensão
if not self._processar_extensao(extensao):
return False, "Extensão inválida"
return True, "Email válido"
except Exception as e:
return False, f"Erro na validação: {str(e)}"
def _processar_parte_local(self, texto):
"""Processa parte local usando AFN"""
estado_atual = {'q0'}
for char in texto:
tipo_char = self._classificar_caractere(char)
novos_estados = set()
for estado in estado_atual:
if (estado, tipo_char) in self.afn_parte_local.transicoes:
novos_estados.update(
self.afn_parte_local.transicoes[(estado, tipo_char)]
)
estado_atual = novos_estados
if not estado_atual:
return False
return bool(estado_atual.intersection(self.afn_parte_local.estados_finais))
def _classificar_caractere(self, char):
"""Classifica caractere para processamento pelo AFN"""
if char.isalpha():
return 'letra'
elif char.isdigit():
return 'numero'
else:
return char
# Teste prático
validador = ValidadorEmailAFN()
emails_teste = [
"usuario@exemplo.com",
"joao.silva@empresa.com.br",
"teste123@sub.dominio.org",
"@exemplo.com", # Inválido
"usuario@.com", # Inválido
"user@domain", # Inválido
]
for email in emails_teste:
valido, mensagem = validador.validar_email(email)
print(f"{email}: {'✓' if valido else '✗'} - {mensagem}")class ValidadorEmailAFN {
constructor() {
this.afnParteLocal = this._construirParteLocal();
this.afnDominio = this._construirDominio();
this.afnExtensao = this._construirExtensao();
}
_construirParteLocal() {
const transicoes = new Map([
['q0,letra', ['q1']],
['q0,numero', ['q1']],
['q1,letra', ['q1']],
['q1,numero', ['q1']],
['q1,.', ['q2']],
['q1,_', ['q2']],
['q2,letra', ['q1']],
['q2,numero', ['q1']]
]);
return new AFN(
['q0', 'q1', 'q2'],
['letra', 'numero', '.', '_'],
transicoes,
'q0',
['q1']
);
}
_construirDominio() {
const transicoes = new Map([
['d0,letra', ['d1']],
['d0,numero', ['d1']],
['d1,letra', ['d1']],
['d1,numero', ['d1']],
['d1,-', ['d2']],
['d2,letra', ['d1']],
['d2,numero', ['d1']]
]);
return new AFN(
['d0', 'd1', 'd2'],
['letra', 'numero', '-'],
transicoes,
'd0',
['d1']
);
}
_construirExtensao() {
const transicoes = new Map([
['e0,letra', ['e1']],
['e1,letra', ['e2']],
['e2,letra', ['e3']],
['e3,letra', ['e4']]
]);
return new AFN(
['e0', 'e1', 'e2', 'e3', 'e4'],
['letra'],
transicoes,
'e0',
['e2', 'e3', 'e4']
);
}
validarEmail(email) {
const partes = email.split('@');
if (partes.length !== 2) {
return { valido: false, erro: "Email deve conter exatamente um @" };
}
const [parteLocal, dominioCompleto] = partes;
// Valida parte local
if (!this._processarTexto(parteLocal, this.afnParteLocal)) {
return { valido: false, erro: "Parte local inválida" };
}
// Processa domínio e extensão
const partesDominio = dominioCompleto.split('.');
if (partesDominio.length < 2) {
return { valido: false, erro: "Domínio deve conter pelo menos um ponto" };
}
const extensao = partesDominio.pop();
const dominio = partesDominio.join('.');
if (!this._processarTexto(dominio, this.afnDominio)) {
return { valido: false, erro: "Domínio inválido" };
}
if (!this._processarTexto(extensao, this.afnExtensao)) {
return { valido: false, erro: "Extensão inválida" };
}
return { valido: true, erro: null };
}
_processarTexto(texto, afn) {
let estadosAtivos = new Set([afn.estadoInicial]);
for (const char of texto) {
const tipoChar = this._classificarCaractere(char);
const novosEstados = new Set();
for (const estado of estadosAtivos) {
const chave = `${estado},${tipoChar}`;
if (afn.transicoes.has(chave)) {
for (const destino of afn.transicoes.get(chave)) {
novosEstados.add(destino);
}
}
}
estadosAtivos = novosEstados;
if (estadosAtivos.size === 0) return false;
}
return [...estadosAtivos].some(estado => afn.estadosFinais.has(estado));
}
_classificarCaractere(char) {
if (/[a-zA-Z]/.test(char)) return 'letra';
if (/[0-9]/.test(char)) return 'numero';
return char;
}
}
// Exemplo de uso
const validador = new ValidadorEmailAFN();
const emailsTeste = [
"usuario@exemplo.com",
"joao.silva@empresa.com.br",
"invalid@",
"@invalid.com"
];
emailsTeste.forEach(email => {
const resultado = validador.validarEmail(email);
console.log(`${email}: ${resultado.valido ? '✓' : '✗'} ${resultado.erro || ''}`);
});Caso Real 2: Análise de Logs de Servidor Web 🌐
Considere que você trabalha como engenheiro de DevOps e precisa analisar milhões de linhas de logs de servidores web Apache/Nginx para identificar padrões específicos de acesso suspeito, como tentativas de ataques SQL injection ou XSS.
O Desafio Real: Logs de servidor contêm informações estruturadas complexas: IP, timestamp, método HTTP, URL, código de resposta, user agent. Identificar padrões maliciosos requer reconhecimento de múltiplas características simultaneamente.
Exemplo de Entrada de Log:
192.168.1.100 - - [25/Dec/2023:10:30:45 +0000] "GET /admin/users.php?id=1' OR '1'='1 HTTP/1.1" 200 1234 "Mozilla/5.0..."Solução com AFN - Construção por Antecipação:
graph TB
subgraph "AFN para Detecção de SQL Injection"
A[Início] --> B[IP Address]
B --> C[Timestamp]
C --> D[Método HTTP]
D --> E[URL Path]
E --> F{Contém caracteres suspeitos?}
F -->|Sim| G[Modo Suspeito]
F -->|Não| H[Modo Normal]
G --> I[Busca padrões SQL]
I --> J[DETECTADO]
H --> K[Log Normal]
end
style J fill:#FF6B6B
style G fill:#FFE66D
style I fill:#FF8E53
import re
from datetime import datetime
from collections import defaultdict
class AnalisadorLogsAFN:
def __init__(self):
self.afn_sql_injection = self._construir_detector_sql()
self.afn_xss = self._construir_detector_xss()
self.afn_brute_force = self._construir_detector_brute_force()
self.contadores_suspeitas = defaultdict(int)
def _construir_detector_sql(self):
"""AFN para detectar tentativas de SQL injection"""
estados = {'inicio', 'url', 'parametro', 'suspeito_sql', 'confirmado_sql'}
transicoes = {
('inicio', 'ip'): {'inicio'},
('inicio', 'metodo'): {'url'},
('url', 'path'): {'parametro'},
('parametro', '?'): {'parametro'},
('parametro', '='): {'parametro'},
('parametro', '\''): {'suspeito_sql'},
('parametro', 'union'): {'confirmado_sql'},
('parametro', 'select'): {'confirmado_sql'},
('parametro', 'drop'): {'confirmado_sql'},
('suspeito_sql', 'or'): {'confirmado_sql'},
('suspeito_sql', 'and'): {'confirmado_sql'},
('suspeito_sql', '1=1'): {'confirmado_sql'},
}
return AFN(estados,
{'ip', 'metodo', 'path', '?', '=', '\'', 'union', 'select', 'drop', 'or', 'and', '1=1'},
transicoes, 'inicio', {'confirmado_sql'})
def _construir_detector_xss(self):
"""AFN para detectar tentativas de XSS"""
estados = {'inicio', 'url', 'script_inicio', 'script_completo', 'detectado_xss'}
transicoes = {
('inicio', 'qualquer'): {'inicio', 'url'},
('url', '<'): {'script_inicio'},
('script_inicio', 'script'): {'script_completo'},
('script_completo', 'alert'): {'detectado_xss'},
('script_completo', 'document'): {'detectado_xss'},
('script_completo', 'window'): {'detectado_xss'},
}
return AFN(estados,
{'qualquer', '<', 'script', 'alert', 'document', 'window'},
transicoes, 'inicio', {'detectado_xss'})
def _construir_detector_brute_force(self):
"""AFN para detectar tentativas de força bruta em login"""
estados = {'inicio', 'login_url', 'post_detectado', 'erro_detectado', 'suspeita_brute_force'}
transicoes = {
('inicio', 'qualquer'): {'inicio'},
('inicio', '/login'): {'login_url'},
('inicio', '/admin'): {'login_url'},
('login_url', 'POST'): {'post_detectado'},
('post_detectado', '401'): {'erro_detectado'},
('post_detectado', '403'): {'erro_detectado'},
('erro_detectado', 'mesmo_ip'): {'suspeita_brute_force'},
}
return AFN(estados,
{'qualquer', '/login', '/admin', 'POST', '401', '403', 'mesmo_ip'},
transicoes, 'inicio', {'suspeita_brute_force'})
def analisar_linha_log(self, linha_log):
"""Analisa uma linha de log usando AFNs"""
try:
# Parse da linha de log (formato Apache/Nginx)
partes = self._parsear_log(linha_log)
if not partes:
return []
alertas = []
# Testa SQL injection
if self._testar_sql_injection(partes):
alertas.append({
'tipo': 'SQL_INJECTION',
'ip': partes['ip'],
'url': partes['url'],
'timestamp': partes['timestamp'],
'severidade': 'ALTA'
})
# Testa XSS
if self._testar_xss(partes):
alertas.append({
'tipo': 'XSS',
'ip': partes['ip'],
'url': partes['url'],
'timestamp': partes['timestamp'],
'severidade': 'MÉDIA'
})
# Testa brute force (requer contexto de múltiplas linhas)
if self._testar_brute_force(partes):
alertas.append({
'tipo': 'BRUTE_FORCE',
'ip': partes['ip'],
'url': partes['url'],
'timestamp': partes['timestamp'],
'severidade': 'ALTA'
})
return alertas
except Exception as e:
return [{'tipo': 'ERRO_PARSING', 'erro': str(e)}]
def _parsear_log(self, linha):
"""Faz parsing de linha de log Apache/Nginx"""
# Regex para formato de log comum
padrao = r'(\d+\.\d+\.\d+\.\d+).*?\[(.*?)\] "(\w+) (.*?) HTTP.*?" (\d+) (\d+)'
match = re.match(padrao, linha)
if match:
return {
'ip': match.group(1),
'timestamp': match.group(2),
'metodo': match.group(3),
'url': match.group(4),
'codigo_resposta': match.group(5),
'tamanho_resposta': match.group(6)
}
return None
def _testar_sql_injection(self, partes):
"""Testa se URL contém padrões de SQL injection"""
url = partes['url'].lower()
# Tokeniza URL para AFN
tokens = self._tokenizar_url_sql(url)
# Simula processamento pelo AFN
estados_ativos = {'inicio'}
for token in tokens:
novos_estados = set()
for estado in estados_ativos:
if (estado, token) in self.afn_sql_injection.transicoes:
novos_estados.update(self.afn_sql_injection.transicoes[(estado, token)])
estados_ativos = novos_estados
if not estados_ativos:
break
return 'confirmado_sql' in estados_ativos
def _tokenizar_url_sql(self, url):
"""Converte URL em tokens para análise de SQL injection"""
tokens = []
# Procura por padrões SQL suspeitos
padroes_sql = ['union', 'select', 'drop', 'insert', 'delete', 'update']
padroes_operadores = ['\'', '"', '=', '?', '&']
padroes_condicoes = ['or', 'and', '1=1', '1=0']
url_lower = url.lower()
for padrao in padroes_sql:
if padrao in url_lower:
tokens.append(padrao)
for padrao in padroes_operadores:
if padrao in url:
tokens.append(padrao)
for padrao in padroes_condicoes:
if padrao in url_lower:
tokens.append(padrao)
return tokens
def _testar_xss(self, partes):
"""Testa se URL contém padrões de XSS"""
url = partes['url'].lower()
# Procura por padrões XSS comuns
padroes_xss = ['<script', 'javascript:', 'alert(', 'document.', 'window.', 'eval(']
return any(padrao in url for padrao in padroes_xss)
def _testar_brute_force(self, partes):
"""Testa padrões de brute force (simplificado)"""
ip = partes['ip']
codigo = partes['codigo_resposta']
url = partes['url'].lower()
# Conta tentativas de login falhadas por IP
if '/login' in url or '/admin' in url:
if codigo in ['401', '403', '500']:
self.contadores_suspeitas[ip] += 1
# Se mais de 5 tentativas falhadas, é suspeito
return self.contadores_suspeitas[ip] > 5
return False
# Exemplo de uso com logs reais
def demonstrar_analise_logs():
analisador = AnalisadorLogsAFN()
# Logs de exemplo (alguns suspeitos, alguns normais)
logs_exemplo = [
"192.168.1.100 - - [25/Dec/2023:10:30:45 +0000] \"GET /index.php HTTP/1.1\" 200 1234",
"192.168.1.101 - - [25/Dec/2023:10:31:15 +0000] \"GET /admin/users.php?id=1' OR '1'='1 HTTP/1.1\" 200 1234",
"192.168.1.102 - - [25/Dec/2023:10:32:00 +0000] \"GET /search?q=<script>alert('xss')</script> HTTP/1.1\" 200 567",
"192.168.1.103 - - [25/Dec/2023:10:33:10 +0000] \"POST /login HTTP/1.1\" 401 89",
"192.168.1.103 - - [25/Dec/2023:10:33:15 +0000] \"POST /login HTTP/1.1\" 401 89",
"192.168.1.104 - - [25/Dec/2023:10:34:20 +0000] \"GET /products.php?category=electronics HTTP/1.1\" 200 2345"
]
print("🔍 Análise de Logs de Segurança\n")
for i, linha in enumerate(logs_exemplo, 1):
print(f"Log {i}:")
print(f" {linha}")
alertas = analisador.analisar_linha_log(linha)
if alertas:
for alerta in alertas:
if alerta['tipo'] != 'ERRO_PARSING':
print(f" 🚨 ALERTA: {alerta['tipo']} - Severidade: {alerta['severidade']}")
print(f" IP: {alerta['ip']}, URL: {alerta['url']}")
else:
print(" ✅ Log normal - sem ameaças detectadas")
print()
# Executa demonstração
demonstrar_analise_logs()import java.util.*;
import java.util.regex.*;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
public class AnalisadorLogsAFN {
private AFN afnSqlInjection;
private AFN afnXSS;
private Map<String, Integer> contadoresSuspeitas;
public AnalisadorLogsAFN() {
this.afnSqlInjection = construirDetectorSQL();
this.afnXSS = construirDetectorXSS();
this.contadoresSuspeitas = new HashMap<>();
}
private AFN construirDetectorSQL() {
Set<String> estados = Set.of("inicio", "url", "parametro", "suspeito_sql", "confirmado_sql");
Set<String> alfabeto = Set.of("ip", "metodo", "path", "?", "=", "'", "union", "select", "drop", "or", "and", "1=1");
Map<String, Set<String>> transicoes = new HashMap<>();
transicoes.put("inicio,ip", Set.of("inicio"));
transicoes.put("inicio,metodo", Set.of("url"));
transicoes.put("url,path", Set.of("parametro"));
transicoes.put("parametro,?", Set.of("parametro"));
transicoes.put("parametro,=", Set.of("parametro"));
transicoes.put("parametro,'", Set.of("suspeito_sql"));
transicoes.put("parametro,union", Set.of("confirmado_sql"));
transicoes.put("parametro,select", Set.of("confirmado_sql"));
transicoes.put("suspeito_sql,or", Set.of("confirmado_sql"));
transicoes.put("suspeito_sql,1=1", Set.of("confirmado_sql"));
return new AFN(estados, alfabeto, transicoes, "inicio", Set.of("confirmado_sql"));
}
private AFN construirDetectorXSS() {
Set<String> estados = Set.of("inicio", "script_inicio", "detectado_xss");
Set<String> alfabeto = Set.of("qualquer", "<", "script", "alert", "document");
Map<String, Set<String>> transicoes = new HashMap<>();
transicoes.put("inicio,qualquer", Set.of("inicio"));
transicoes.put("inicio,<", Set.of("script_inicio"));
transicoes.put("script_inicio,script", Set.of("detectado_xss"));
transicoes.put("inicio,alert", Set.of("detectado_xss"));
transicoes.put("inicio,document", Set.of("detectado_xss"));
return new AFN(estados, alfabeto, transicoes, "inicio", Set.of("detectado_xss"));
}
public List<AlertaSeguranca> analisarLinhaLog(String linhaLog) {
List<AlertaSeguranca> alertas = new ArrayList<>();
try {
LogEntry entrada = parsearLog(linhaLog);
if (entrada == null) return alertas;
// Testa SQL Injection
if (testarSQLInjection(entrada)) {
alertas.add(new AlertaSeguranca(
"SQL_INJECTION",
entrada.ip,
entrada.url,
entrada.timestamp,
"ALTA"
));
}
// Testa XSS
if (testarXSS(entrada)) {
alertas.add(new AlertaSeguranca(
"XSS",
entrada.ip,
entrada.url,
entrada.timestamp,
"MÉDIA"
));
}
// Testa Brute Force
if (testarBruteForce(entrada)) {
alertas.add(new AlertaSeguranca(
"BRUTE_FORCE",
entrada.ip,
entrada.url,
entrada.timestamp,
"ALTA"
));
}
} catch (Exception e) {
alertas.add(new AlertaSeguranca("ERRO_PARSING", "", "", "", e.getMessage()));
}
return alertas;
}
private LogEntry parsearLog(String linha) {
// Regex para formato Apache/Nginx
String padrao = "(\\d+\\.\\d+\\.\\d+\\.\\d+).*?\\[(.*?)\\] \"(\\w+) (.*?) HTTP.*?\" (\\d+) (\\d+)";
Pattern pattern = Pattern.compile(padrao);
Matcher matcher = pattern.matcher(linha);
if (matcher.find()) {
return new LogEntry(
matcher.group(1), // IP
matcher.group(2), // Timestamp
matcher.group(3), // Método
matcher.group(4), // URL
matcher.group(5), // Código de resposta
matcher.group(6) // Tamanho
);
}
return null;
}
private boolean testarSQLInjection(LogEntry entrada) {
String url = entrada.url.toLowerCase();
List<String> tokens = tokenizarURLSQL(url);
Set<String> estadosAtivos = new HashSet<>(Arrays.asList("inicio"));
for (String token : tokens) {
Set<String> novosEstados = new HashSet<>();
for (String estado : estadosAtivos) {
String chave = estado + "," + token;
Set<String> destinos = afnSqlInjection.getTransicoes().get(chave);
if (destinos != null) {
novosEstados.addAll(destinos);
}
}
estadosAtivos = novosEstados;
if (estadosAtivos.isEmpty()) break;
}
return estadosAtivos.contains("confirmado_sql");
}
private List<String> tokenizarURLSQL(String url) {
List<String> tokens = new ArrayList<>();
String[] padroesSql = {"union", "select", "drop", "insert", "delete"};
String[] padroesOperadores = {"'", "\"", "=", "?", "&"};
String[] padroesCondicoes = {"or", "and", "1=1", "1=0"};
for (String padrao : padroesSql) {
if (url.contains(padrao)) tokens.add(padrao);
}
for (String padrao : padroesOperadores) {
if (url.contains(padrao)) tokens.add(padrao);
}
for (String padrao : padroesCondicoes) {
if (url.contains(padrao)) tokens.add(padrao);
}
return tokens;
}
private boolean testarXSS(LogEntry entrada) {
String url = entrada.url.toLowerCase();
String[] padroesXSS = {"<script", "javascript:", "alert(", "document.", "window.", "eval("};
return Arrays.stream(padroesXSS).anyMatch(url::contains);
}
private boolean testarBruteForce(LogEntry entrada) {
String ip = entrada.ip;
String codigo = entrada.codigoResposta;
String url = entrada.url.toLowerCase();
if ((url.contains("/login") || url.contains("/admin")) &&
(codigo.equals("401") || codigo.equals("403"))) {
contadoresSuspeitas.merge(ip, 1, Integer::sum);
return contadoresSuspeitas.get(ip) > 5;
}
return false;
}
// Classes auxiliares
static class LogEntry {
String ip, timestamp, metodo, url, codigoResposta, tamanho;
LogEntry(String ip, String timestamp, String metodo, String url, String codigoResposta, String tamanho) {
this.ip = ip;
this.timestamp = timestamp;
this.metodo = metodo;
this.url = url;
this.codigoResposta = codigoResposta;
this.tamanho = tamanho;
}
}
static class AlertaSeguranca {
String tipo, ip, url, timestamp, severidade;
AlertaSeguranca(String tipo, String ip, String url, String timestamp, String severidade) {
this.tipo = tipo;
this.ip = ip;
this.url = url;
this.timestamp = timestamp;
this.severidade = severidade;
}
@Override
public String toString() {
return String.format("🚨 %s [%s] - IP: %s, URL: %s", tipo, severidade, ip, url);
}
}
// Método de demonstração
public static void main(String[] args) {
AnalisadorLogsAFN analisador = new AnalisadorLogsAFN();
String[] logsExemplo = {
"192.168.1.100 - - [25/Dec/2023:10:30:45 +0000] \"GET /index.php HTTP/1.1\" 200 1234",
"192.168.1.101 - - [25/Dec/2023:10:31:15 +0000] \"GET /admin/users.php?id=1' OR '1'='1 HTTP/1.1\" 200 1234",
"192.168.1.102 - - [25/Dec/2023:10:32:00 +0000] \"GET /search?q=<script>alert('xss')</script> HTTP/1.1\" 200 567"
};
System.out.println("🔍 Análise de Logs de Segurança\n");
for (int i = 0; i < logsExemplo.length; i++) {
System.out.println("Log " + (i + 1) + ":");
System.out.println(" " + logsExemplo[i]);
List<AlertaSeguranca> alertas = analisador.analisarLinhaLog(logsExemplo[i]);
if (!alertas.isEmpty()) {
alertas.forEach(alerta -> System.out.println(" " + alerta));
} else {
System.out.println(" ✅ Log normal - sem ameaças detectadas");
}
System.out.println();
}
}
}Caso Real 3: Reconhecimento de Padrões em Código-Fonte 💻
Imagine que você está desenvolvendo um sistema de análise estática de código para detectar vulnerabilidades de segurança em aplicações web. O sistema deve identificar padrões perigosos como concatenação direta de strings em queries SQL, uso inadequado de funções eval(), e validação insuficiente de entrada de usuário.
O Desafio Técnico: Código-fonte tem estrutura complexa com aninhamento, comentários, strings, e múltiplas linguagens. Detectar padrões perigosos requer reconhecimento contextual sofisticado que considere escopo, tipo de dados, e fluxo de execução.
Solução com AFN - Padrão de Confirmação Múltipla:
graph TB
subgraph "AFN para Detecção de SQL Injection no Código"
A[Início] --> B[Busca por Query SQL]
B --> C[String Concatenação]
C --> D[Variável de Entrada]
D --> E[Sem Validação]
E --> F[VULNERABILIDADE]
B --> G[Query Parametrizada]
G --> H[Prepared Statement]
H --> I[SEGURO]
subgraph "Estados Paralelos"
J["Busca por eval()"]
K[Busca por innerHTML]
L[Busca por document.write]
end
A --> J
A --> K
A --> L
end
style F fill:#FF6B6B
style I fill:#51CF66
style J fill:#FFE66D
style K fill:#FFE66D
style L fill:#FFE66D
import re
import ast
from typing import List, Dict, Set, Tuple
class AnalisadorCodigoAFN:
def __init__(self):
self.afn_sql_injection = self._construir_detector_sql_injection()
self.afn_xss = self._construir_detector_xss()
self.afn_eval_perigoso = self._construir_detector_eval()
self.vulnerabilidades_encontradas = []
def _construir_detector_sql_injection(self):
"""AFN para detectar vulnerabilidades de SQL injection"""
estados = {
'inicio', 'string_sql', 'concatenacao', 'variavel_externa',
'vulneravel', 'prepared_statement', 'seguro'
}
transicoes = {
('inicio', 'SELECT'): {'string_sql'},
('inicio', 'INSERT'): {'string_sql'},
('inicio', 'UPDATE'): {'string_sql'},
('inicio', 'DELETE'): {'string_sql'},
('string_sql', '+'): {'concatenacao'},
('string_sql', 'format'): {'concatenacao'},
('string_sql', '%'): {'concatenacao'},
('concatenacao', 'input_usuario'): {'variavel_externa'},
('concatenacao', 'request'): {'variavel_externa'},
('concatenacao', 'GET'): {'variavel_externa'},
('concatenacao', 'POST'): {'variavel_externa'},
('variavel_externa', 'sem_sanitizacao'): {'vulneravel'},
('string_sql', 'prepare'): {'prepared_statement'},
('string_sql', 'bind_param'): {'prepared_statement'},
('prepared_statement', 'execute'): {'seguro'}
}
return AFN(estados, set(), transicoes, 'inicio', {'vulneravel', 'seguro'})
def _construir_detector_xss(self):
"""AFN para detectar vulnerabilidades XSS"""
estados = {
'inicio', 'output_html', 'variavel_usuario', 'sem_escape',
'vulneravel_xss', 'com_escape', 'seguro_xss'
}
transicoes = {
('inicio', 'innerHTML'): {'output_html'},
('inicio', 'document.write'): {'output_html'},
('inicio', 'outerHTML'): {'output_html'},
('inicio', 'echo'): {'output_html'},
('inicio', 'print'): {'output_html'},
('output_html', 'variavel'): {'variavel_usuario'},
('variavel_usuario', 'sem_validacao'): {'sem_escape'},
('sem_escape', 'direto'): {'vulneravel_xss'},
('variavel_usuario', 'escape'): {'com_escape'},
('variavel_usuario', 'sanitize'): {'com_escape'},
('com_escape', 'output'): {'seguro_xss'}
}
return AFN(estados, set(), transicoes, 'inicio', {'vulneravel_xss', 'seguro_xss'})
def _construir_detector_eval(self):
"""AFN para detectar uso perigoso de eval()"""
estados = {
'inicio', 'eval_chamada', 'input_dinamico', 'vulneravel_eval'
}
transicoes = {
('inicio', 'eval'): {'eval_chamada'},
('inicio', 'exec'): {'eval_chamada'},
('inicio', 'Function'): {'eval_chamada'},
('eval_chamada', 'input_usuario'): {'input_dinamico'},
('eval_chamada', 'request'): {'input_dinamico'},
('input_dinamico', 'sem_validacao'): {'vulneravel_eval'}
}
return AFN(estados, set(), transicoes, 'inicio', {'vulneravel_eval'})
def analisar_arquivo_codigo(self, caminho_arquivo: str, linguagem: str) -> List[Dict]:
"""Analisa arquivo de código para vulnerabilidades"""
try:
with open(caminho_arquivo, 'r', encoding='utf-8') as arquivo:
codigo = arquivo.read()
if linguagem.lower() == 'python':
return self._analisar_python(codigo, caminho_arquivo)
elif linguagem.lower() in ['javascript', 'js']:
return self._analisar_javascript(codigo, caminho_arquivo)
elif linguagem.lower() == 'php':
return self._analisar_php(codigo, caminho_arquivo)
else:
return self._analisar_generico(codigo, caminho_arquivo)
except Exception as e:
return [{'erro': f'Erro ao analisar {caminho_arquivo}: {str(e)}'}]
def _analisar_python(self, codigo: str, arquivo: str) -> List[Dict]:
"""Análise específica para Python"""
vulnerabilidades = []
linhas = codigo.split('\n')
for i, linha in enumerate(linhas, 1):
linha_lower = linha.lower().strip()
# Detecção de SQL injection
if self._detectar_sql_injection_python(linha_lower):
vulnerabilidades.append({
'tipo': 'SQL_INJECTION',
'arquivo': arquivo,
'linha': i,
'codigo': linha.strip(),
'severidade': 'ALTA',
'descricao': 'Possível SQL injection - concatenação direta de strings em query'
})
# Detecção de eval perigoso
if self._detectar_eval_perigoso_python(linha_lower):
vulnerabilidades.append({
'tipo': 'CODE_INJECTION',
'arquivo': arquivo,
'linha': i,
'codigo': linha.strip(),
'severidade': 'CRÍTICA',
'descricao': 'Uso perigoso de eval() com entrada não validada'
})
# Detecção de XSS em templates
if self._detectar_xss_python(linha_lower):
vulnerabilidades.append({
'tipo': 'XSS',
'arquivo': arquivo,
'linha': i,
'codigo': linha.strip(),
'severidade': 'MÉDIA',
'descricao': 'Possível XSS - output sem escape adequado'
})
return vulnerabilidades
def _detectar_sql_injection_python(self, linha: str) -> bool:
"""Usa AFN para detectar padrões de SQL injection em Python"""
# Simula processamento pelo AFN
tokens = self._tokenizar_linha_sql(linha)
estados_ativos = {'inicio'}
for token in tokens:
novos_estados = set()
for estado in estados_ativos:
if (estado, token) in self.afn_sql_injection.transicoes:
novos_estados.update(self.afn_sql_injection.transicoes[(estado, token)])
estados_ativos = novos_estados
if not estados_ativos:
break
return 'vulneravel' in estados_ativos
def _tokenizar_linha_sql(self, linha: str) -> List[str]:
"""Converte linha de código em tokens para análise SQL"""
tokens = []
# Padrões SQL
if re.search(r'\b(select|insert|update|delete)\b', linha):
tokens.extend(re.findall(r'\b(select|insert|update|delete)\b', linha))
# Padrões de concatenação
if '+' in linha or '.format(' in linha or '%' in linha:
if '+' in linha: tokens.append('+')
if '.format(' in linha: tokens.append('format')
if '%' in linha: tokens.append('%')
# Padrões de entrada de usuário
if re.search(r'\b(request|input|sys\.argv)\b', linha):
tokens.append('input_usuario')
# Verifica se há sanitização
if not re.search(r'\b(escape|sanitize|validate)\b', linha):
tokens.append('sem_sanitizacao')
return tokens
def _analisar_javascript(self, codigo: str, arquivo: str) -> List[Dict]:
"""Análise específica para JavaScript"""
vulnerabilidades = []
linhas = codigo.split('\n')
for i, linha in enumerate(linhas, 1):
linha_lower = linha.lower().strip()
# Detecção de XSS
if self._detectar_xss_javascript(linha_lower):
vulnerabilidades.append({
'tipo': 'XSS',
'arquivo': arquivo,
'linha': i,
'codigo': linha.strip(),
'severidade': 'ALTA',
'descricao': 'Possível XSS - manipulação DOM sem validação'
})
# Detecção de eval perigoso
if self._detectar_eval_javascript(linha_lower):
vulnerabilidades.append({
'tipo': 'CODE_INJECTION',
'arquivo': arquivo,
'linha': i,
'codigo': linha.strip(),
'severidade': 'CRÍTICA',
'descricao': 'Uso perigoso de eval() ou Function()'
})
return vulnerabilidades
def _detectar_xss_javascript(self, linha: str) -> bool:
"""Detecta padrões XSS em JavaScript"""
padroes_perigosos = [
r'\.innerhtml\s*=.*\+',
r'document\.write\s*\(',
r'\.outerhtml\s*=.*\+',
r'\$\([^)]+\)\.html\('
]
for padrao in padroes_perigosos:
if re.search(padrao, linha):
# Verifica se não há escape
if not re.search(r'\b(escape|sanitize|encodehtmlentities)\b', linha):
return True
return False
def _detectar_eval_javascript(self, linha: str) -> bool:
"""Detecta uso perigoso de eval em JavaScript"""
if re.search(r'\beval\s*\(', linha) or re.search(r'new\s+function\s*\(', linha):
# Verifica se usa entrada do usuário
if re.search(r'\b(prompt|location\.|document\.|window\.)', linha):
return True
return False
def _detectar_eval_perigoso_python(self, linha: str) -> bool:
"""Detecta uso perigoso de eval em Python"""
if re.search(r'\b(eval|exec)\s*\(', linha):
if re.search(r'\b(input|sys\.argv|request)\b', linha):
return True
return False
def _detectar_xss_python(self, linha: str) -> bool:
"""Detecta XSS em templates Python"""
if re.search(r'render.*\|safe', linha) or re.search(r'mark_safe\(', linha):
if re.search(r'\b(request|input)\b', linha):
return True
return False
# Exemplo de uso prático
def demonstrar_analise_codigo():
analisador = AnalisadorCodigoAFN()
# Código Python vulnerável (exemplo)
codigo_python_vulneravel = '''
def buscar_usuario(user_id):
# VULNERÁVEL: SQL injection
query = "SELECT * FROM users WHERE id = " + user_id
cursor.execute(query)
def processar_entrada():
# VULNERÁVEL: Code injection
codigo = input("Digite código Python: ")
eval(codigo)
def exibir_mensagem(msg):
# VULNERÁVEL: XSS em template
return render_template('page.html', content=msg|safe)
'''
# Código JavaScript vulnerável (exemplo)
codigo_js_vulneravel = '''
function exibirMensagem(userInput) {
// VULNERÁVEL: XSS
document.getElementById('content').innerHTML = userInput;
}
function executarComando() {
// VULNERÁVEL: Code injection
var comando = prompt("Digite comando:");
eval(comando);
}
'''
print("🔍 Análise de Vulnerabilidades em Código\n")
# Salva códigos em arquivos temporários para teste
import tempfile
import os
with tempfile.NamedTemporaryFile(mode='w', suffix='.py', delete=False) as f:
f.write(codigo_python_vulneravel)
arquivo_python = f.name
with tempfile.NamedTemporaryFile(mode='w', suffix='.js', delete=False) as f:
f.write(codigo_js_vulneravel)
arquivo_js = f.name
try:
# Analisa código Python
print("📄 Analisando código Python:")
vulnerabilidades_py = analisador.analisar_arquivo_codigo(arquivo_python, 'python')
for vuln in vulnerabilidades_py:
if 'erro' not in vuln:
print(f" 🚨 {vuln['tipo']} (Linha {vuln['linha']}) - {vuln['severidade']}")
print(f" {vuln['descricao']}")
print(f" Código: {vuln['codigo']}")
print()
# Analisa código JavaScript
print("📄 Analisando código JavaScript:")
vulnerabilidades_js = analisador.analisar_arquivo_codigo(arquivo_js, 'javascript')
for vuln in vulnerabilidades_js:
if 'erro' not in vuln:
print(f" 🚨 {vuln['tipo']} (Linha {vuln['linha']}) - {vuln['severidade']}")
print(f" {vuln['descricao']}")
print(f" Código: {vuln['codigo']}")
print()
# Estatísticas
total_vulns = len([v for v in vulnerabilidades_py + vulnerabilidades_js if 'erro' not in v])
print(f"📊 Total de vulnerabilidades encontradas: {total_vulns}")
finally:
# Limpa arquivos temporários
os.unlink(arquivo_python)
os.unlink(arquivo_js)
# Executa demonstração
demonstrar_analise_codigo()class AnalisadorCodigoAFN {
constructor() {
this.afnSqlInjection = this._construirDetectorSqlInjection();
this.afnXSS = this._construirDetectorXSS();
this.afnEval = this._construirDetectorEval();
}
_construirDetectorSqlInjection() {
const transicoes = new Map([
['inicio,SELECT', ['string_sql']],
['inicio,INSERT', ['string_sql']],
['inicio,UPDATE', ['string_sql']],
['inicio,DELETE', ['string_sql']],
['string_sql,+', ['concatenacao']],
['string_sql,template', ['concatenacao']],
['concatenacao,input_usuario', ['variavel_externa']],
['concatenacao,request', ['variavel_externa']],
['variavel_externa,sem_sanitizacao', ['vulneravel']],
['string_sql,prepare', ['prepared_statement']],
['prepared_statement,execute', ['seguro']]
]);
return new AFN(
['inicio', 'string_sql', 'concatenacao', 'variavel_externa', 'vulneravel', 'prepared_statement', 'seguro'],
['SELECT', 'INSERT', 'UPDATE', 'DELETE', '+', 'template', 'input_usuario', 'request', 'sem_sanitizacao', 'prepare', 'execute'],
transicoes,
'inicio',
['vulneravel', 'seguro']
);
}
_construirDetectorXSS() {
const transicoes = new Map([
['inicio,innerHTML', ['output_html']],
['inicio,document.write', ['output_html']],
['inicio,outerHTML', ['output_html']],
['output_html,variavel', ['variavel_usuario']],
['variavel_usuario,sem_validacao', ['sem_escape']],
['sem_escape,direto', ['vulneravel_xss']],
['variavel_usuario,escape', ['com_escape']],
['com_escape,output', ['seguro_xss']]
]);
return new AFN(
['inicio', 'output_html', 'variavel_usuario', 'sem_escape', 'vulneravel_xss', 'com_escape', 'seguro_xss'],
['innerHTML', 'document.write', 'outerHTML', 'variavel', 'sem_validacao', 'direto', 'escape', 'output'],
transicoes,
'inicio',
['vulneravel_xss', 'seguro_xss']
);
}
_construirDetectorEval() {
const transicoes = new Map([
['inicio,eval', ['eval_chamada']],
['inicio,Function', ['eval_chamada']],
['eval_chamada,input_usuario', ['input_dinamico']],
['input_dinamico,sem_validacao', ['vulneravel_eval']]
]);
return new AFN(
['inicio', 'eval_chamada', 'input_dinamico', 'vulneravel_eval'],
['eval', 'Function', 'input_usuario', 'sem_validacao'],
transicoes,
'inicio',
['vulneravel_eval']
);
}
analisarCodigo(codigo, linguagem, nomeArquivo = 'codigo') {
const linhas = codigo.split('\n');
const vulnerabilidades = [];
linhas.forEach((linha, indice) => {
const numeroLinha = indice + 1;
const linhaTrimmed = linha.trim().toLowerCase();
// Detecta SQL Injection
if (this._detectarSqlInjection(linhaTrimmed)) {
vulnerabilidades.push({
tipo: 'SQL_INJECTION',
arquivo: nomeArquivo,
linha: numeroLinha,
codigo: linha.trim(),
severidade: 'ALTA',
descricao: 'Possível SQL injection - concatenação direta em query'
});
}
// Detecta XSS
if (this._detectarXSS(linhaTrimmed)) {
vulnerabilidades.push({
tipo: 'XSS',
arquivo: nomeArquivo,
linha: numeroLinha,
codigo: linha.trim(),
severidade: 'ALTA',
descricao: 'Possível XSS - manipulação DOM sem escape'
});
}
// Detecta eval perigoso
if (this._detectarEvalPerigoso(linhaTrimmed)) {
vulnerabilidades.push({
tipo: 'CODE_INJECTION',
arquivo: nomeArquivo,
linha: numeroLinha,
codigo: linha.trim(),
severidade: 'CRÍTICA',
descricao: 'Uso perigoso de eval() com entrada não validada'
});
}
});
return vulnerabilidades;
}
_detectarSqlInjection(linha) {
const tokens = this._tokenizarLinhaSql(linha);
let estadosAtivos = new Set(['inicio']);
for (const token of tokens) {
const novosEstados = new Set();
for (const estado of estadosAtivos) {
const chave = `${estado},${token}`;
if (this.afnSqlInjection.transicoes.has(chave)) {
for (const destino of this.afnSqlInjection.transicoes.get(chave)) {
novosEstados.add(destino);
}
}
}
estadosAtivos = novosEstados;
if (estadosAtivos.size === 0) break;
}
return estadosAtivos.has('vulneravel');
}
_tokenizarLinhaSql(linha) {
const tokens = [];
// Comandos SQL
const comandosSql = ['select', 'insert', 'update', 'delete'];
for (const comando of comandosSql) {
if (linha.includes(comando)) tokens.push(comando.toUpperCase());
}
// Concatenação
if (linha.includes('+') || linha.includes('template') || linha.includes('`${')) {
tokens.push('+');
}
// Entrada de usuário
if (linha.includes('request') || linha.includes('input') || linha.includes('prompt')) {
tokens.push('input_usuario');
}
// Verifica sanitização
if (!linha.includes('escape') && !linha.includes('sanitize') && !linha.includes('validate')) {
tokens.push('sem_sanitizacao');
}
return tokens;
}
_detectarXSS(linha) {
const padroesXSS = [
/\.innerhtml\s*=/,
/document\.write\s*\(/,
/\.outerhtml\s*=/,
/\$\([^)]+\)\.html\(/
];
for (const padrao of padroesXSS) {
if (padrao.test(linha)) {
// Verifica se não há escape
if (!linha.includes('escape') && !linha.includes('sanitize')) {
return true;
}
}
}
return false;
}
_detectarEvalPerigoso(linha) {
if (linha.includes('eval(') || linha.includes('new function')) {
if (linha.includes('prompt') || linha.includes('location.') ||
linha.includes('document.') || linha.includes('window.')) {
return true;
}
}
return false;
}
}
// Demonstração prática
function demonstrarAnaliseCodigoJS() {
const analisador = new AnalisadorCodigoAFN();
const codigoVulneravel = `
function buscarUsuario(userId) {
// VULNERÁVEL: SQL injection
const query = "SELECT * FROM users WHERE id = " + userId;
db.query(query);
}
function exibirMensagem(userInput) {
// VULNERÁVEL: XSS
document.getElementById('content').innerHTML = userInput;
}
function executarComando() {
// VULNERÁVEL: Code injection
const comando = prompt("Digite comando:");
eval(comando);
}
function salvarDados(dados) {
// SEGURO: Prepared statement
const stmt = db.prepare("INSERT INTO tabela VALUES (?, ?)");
stmt.execute(dados.nome, dados.email);
}
`;
console.log("🔍 Análise de Vulnerabilidades em JavaScript\n");
const vulnerabilidades = analisador.analisarCodigo(codigoVulneravel, 'javascript', 'exemplo.js');
vulnerabilidades.forEach(vuln => {
console.log(`🚨 ${vuln.tipo} (Linha ${vuln.linha}) - ${vuln.severidade}`);
console.log(` ${vuln.descricao}`);
console.log(` Código: ${vuln.codigo}`);
console.log();
});
console.log(`📊 Total de vulnerabilidades: ${vulnerabilidades.length}`);
}
// Executar demonstração
demonstrarAnaliseCodigoJS();Caso Real 4: Validação de Configurações de Rede 🌐
Imagine que você trabalha em uma empresa de telecomunicações e precisa desenvolver um sistema para validar arquivos de configuração de roteadores e switches. Estes arquivos contêm configurações complexas de VLAN, ACLs (Access Control Lists), rotas estáticas, e protocolos de roteamento que devem seguir padrões específicos para garantir segurança e funcionalidade da rede.
O Desafio Empresarial: Configurações de rede incorretas podem causar desde perda de conectividade até vulnerabilidades de segurança graves. Um sistema automatizado deve validar milhares de linhas de configuração, detectando inconsistências, configurações perigosas, e violações de políticas corporativas.
Solução com AFN - Construção por Antecipação:
graph TB
subgraph "AFN para Validação de Configurações de Rede"
A[Início] --> B[Seção Config]
B --> C{Tipo de Config}
C -->|VLAN| D[Validar VLAN]
C -->|ACL| E[Validar ACL]
C -->|Route| F[Validar Rota]
C -->|Interface| G[Validar Interface]
D --> H[Verificar Range]
E --> I[Verificar Regras]
F --> J[Verificar Destino]
G --> K[Verificar Status]
H --> L{Válido?}
I --> L
J --> L
K --> L
L -->|Sim| M[CONFIG OK]
L -->|Não| N[CONFIG ERRO]
end
style M fill:#51CF66
style N fill:#FF6B6B
style D fill:#FFE66D
style E fill:#FFE66D
style F fill:#FFE66D
style G fill:#FFE66D
import re
import ipaddress
from typing import List, Dict, Set, Tuple, Optional
from dataclasses import dataclass
@dataclass
class ErroConfiguracao:
linha: int
tipo: str
descricao: str
severidade: str
sugestao: str
class ValidadorConfiguracaoRede:
def __init__(self):
self.afn_vlan = self._construir_validador_vlan()
self.afn_acl = self._construir_validador_acl()
self.afn_rota = self._construir_validador_rota()
self.afn_interface = self._construir_validador_interface()
# Políticas corporativas
self.vlans_permitidas = range(10, 4095) # VLANs permitidas
self.redes_privadas = ['10.0.0.0/8', '172.16.0.0/12', '192.168.0.0/16']
self.portas_proibidas = [22, 23, 135, 139, 445] # Portas que não devem ser abertas
def _construir_validador_vlan(self):
"""AFN para validar configurações de VLAN"""
estados = {
'inicio', 'vlan_cmd', 'vlan_id', 'vlan_name', 'vlan_estado',
'vlan_valida', 'vlan_invalida'
}
transicoes = {
('inicio', 'vlan'): {'vlan_cmd'},
('vlan_cmd', 'numero'): {'vlan_id'},
('vlan_id', 'name'): {'vlan_name'},
('vlan_name', 'string'): {'vlan_estado'},
('vlan_estado', 'active'): {'vlan_valida'},
('vlan_estado', 'suspend'): {'vlan_invalida'},
('vlan_id', 'shutdown'): {'vlan_invalida'}
}
return AFN(estados, set(), transicoes, 'inicio', {'vlan_valida', 'vlan_invalida'})
def _construir_validador_acl(self):
"""AFN para validar Access Control Lists"""
estados = {
'inicio', 'acl_cmd', 'acl_numero', 'permit_deny', 'protocolo',
'origem', 'destino', 'porta', 'acl_valida', 'acl_insegura'
}
transicoes = {
('inicio', 'access-list'): {'acl_cmd'},
('acl_cmd', 'numero'): {'acl_numero'},
('acl_numero', 'permit'): {'permit_deny'},
('acl_numero', 'deny'): {'permit_deny'},
('permit_deny', 'tcp'): {'protocolo'},
('permit_deny', 'udp'): {'protocolo'},
('permit_deny', 'ip'): {'protocolo'},
('protocolo', 'ip_origem'): {'origem'},
('origem', 'ip_destino'): {'destino'},
('destino', 'porta_segura'): {'acl_valida'},
('destino', 'porta_insegura'): {'acl_insegura'},
('destino', 'any'): {'acl_insegura'}
}
return AFN(estados, set(), transicoes, 'inicio', {'acl_valida', 'acl_insegura'})
def _construir_validador_rota(self):
"""AFN para validar rotas estáticas"""
estados = {
'inicio', 'ip_route', 'rede_destino', 'mascara', 'next_hop',
'rota_valida', 'rota_invalida'
}
transicoes = {
('inicio', 'ip'): {'ip_route'},
('ip_route', 'route'): {'rede_destino'},
('rede_destino', 'ip_valido'): {'mascara'},
('mascara', 'mask_valida'): {'next_hop'},
('next_hop', 'gateway_valido'): {'rota_valida'},
('next_hop', 'gateway_invalido'): {'rota_invalida'},
('rede_destino', 'ip_invalido'): {'rota_invalida'}
}
return AFN(estados, set(), transicoes, 'inicio', {'rota_valida', 'rota_invalida'})
def _construir_validador_interface(self):
"""AFN para validar configurações de interface"""
estados = {
'inicio', 'interface_cmd', 'tipo_interface', 'numero_interface',
'config_interface', 'interface_valida', 'interface_problema'
}
transicoes = {
('inicio', 'interface'): {'interface_cmd'},
('interface_cmd', 'ethernet'): {'tipo_interface'},
('interface_cmd', 'fastethernet'): {'tipo_interface'},
('interface_cmd', 'gigabitethernet'): {'tipo_interface'},
('tipo_interface', 'numero'): {'numero_interface'},
('numero_interface', 'no_shutdown'): {'interface_valida'},
('numero_interface', 'shutdown'): {'interface_problema'},
('numero_interface', 'ip_address'): {'config_interface'},
('config_interface', 'ip_valido'): {'interface_valida'}
}
return AFN(estados, set(), transicoes, 'inicio', {'interface_valida', 'interface_problema'})
def validar_arquivo_configuracao(self, caminho_arquivo: str) -> List[ErroConfiguracao]:
"""Valida arquivo completo de configuração"""
try:
with open(caminho_arquivo, 'r', encoding='utf-8') as arquivo:
linhas = arquivo.readlines()
erros = []
contexto_atual = None
for i, linha in enumerate(linhas, 1):
linha_limpa = linha.strip()
if not linha_limpa or linha_limpa.startswith('!'):
continue # Pula linhas vazias e comentários
# Detecta contexto atual
contexto_atual = self._detectar_contexto(linha_limpa, contexto_atual)
# Valida linha baseada no contexto
erros_linha = self._validar_linha(linha_limpa, i, contexto_atual)
erros.extend(erros_linha)
# Validações específicas por tipo
if contexto_atual == 'vlan':
erros_vlan = self._validar_vlan(linha_limpa, i)
erros.extend(erros_vlan)
elif contexto_atual == 'acl':
erros_acl = self._validar_acl(linha_limpa, i)
erros.extend(erros_acl)
elif contexto_atual == 'route':
erros_rota = self._validar_rota(linha_limpa, i)
erros.extend(erros_rota)
elif contexto_atual == 'interface':
erros_interface = self._validar_interface(linha_limpa, i)
erros.extend(erros_interface)
return erros
except Exception as e:
return [ErroConfiguracao(
linha=0,
tipo='ERRO_ARQUIVO',
descricao=f'Erro ao ler arquivo: {str(e)}',
severidade='CRÍTICA',
sugestao='Verifique se o arquivo existe e tem permissões adequadas'
)]
def _detectar_contexto(self, linha: str, contexto_anterior: str) -> str:
"""Detecta o contexto atual da configuração"""
linha_lower = linha.lower()
if linha_lower.startswith('vlan '):
return 'vlan'
elif linha_lower.startswith('access-list'):
return 'acl'
elif linha_lower.startswith('ip route'):
return 'route'
elif linha_lower.startswith('interface'):
return 'interface'
elif linha_lower.startswith('router'):
return 'routing'
elif linha_lower in ['exit', 'end'] or linha_lower.startswith('!'):
return None
else:
return contexto_anterior # Mantém contexto anterior
def _validar_vlan(self, linha: str, numero_linha: int) -> List[ErroConfiguracao]:
"""Valida configurações de VLAN usando AFN"""
erros = []
# Extrai número da VLAN
match = re.search(r'vlan\s+(\d+)', linha.lower())
if match:
vlan_id = int(match.group(1))
# Verifica se VLAN está no range permitido
if vlan_id not in self.vlans_permitidas:
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='VLAN_FORA_RANGE',
descricao=f'VLAN {vlan_id} fora do range permitido (10-4094)',
severidade='ALTA',
sugestao=f'Use VLAN entre {min(self.vlans_permitidas)} e {max(self.vlans_permitidas)}'
))
# Verifica VLANs reservadas
if vlan_id in [1, 1002, 1003, 1004, 1005]:
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='VLAN_RESERVADA',
descricao=f'VLAN {vlan_id} é reservada do sistema',
severidade='CRÍTICA',
sugestao='Use uma VLAN não reservada'
))
# Verifica se VLAN tem nome
if 'vlan' in linha.lower() and 'name' not in linha.lower():
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='VLAN_SEM_NOME',
descricao='VLAN configurada sem nome descritivo',
severidade='MÉDIA',
sugestao='Adicione comando "name <nome_descritivo>"'
))
return erros
def _validar_acl(self, linha: str, numero_linha: int) -> List[ErroConfiguracao]:
"""Valida Access Control Lists"""
erros = []
linha_lower = linha.lower()
# Verifica regras permissivas demais
if 'permit' in linha_lower and 'any any' in linha_lower:
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='ACL_MUITO_PERMISSIVA',
descricao='Regra ACL permite tráfego de qualquer origem para qualquer destino',
severidade='CRÍTICA',
sugestao='Restrinja origem e destino para IPs/redes específicas'
))
# Verifica portas perigosas
for porta in self.portas_proibidas:
if f'eq {porta}' in linha_lower and 'permit' in linha_lower:
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='PORTA_INSEGURA',
descricao=f'ACL permite acesso à porta {porta} (considerada insegura)',
severidade='ALTA',
sugestao=f'Bloqueie ou restrinja acesso à porta {porta}'
))
# Verifica se há regra deny implícita no final
if 'access-list' in linha_lower and 'permit' in linha_lower:
# Simples verificação - em implementação real, verificaria todo o contexto
if not any('deny' in l for l in [linha_lower]): # Verificação simplificada
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='ACL_SEM_DENY_FINAL',
descricao='ACL pode não ter regra deny implícita adequada',
severidade='MÉDIA',
sugestao='Verifique se há regra deny no final da ACL'
))
return erros
def _validar_rota(self, linha: str, numero_linha: int) -> List[ErroConfiguracao]:
"""Valida rotas estáticas"""
erros = []
# Extrai IPs da linha de rota
ips = re.findall(r'\b(?:\d{1,3}\.){3}\d{1,3}\b', linha)
for ip_str in ips:
try:
ip = ipaddress.IPv4Address(ip_str)
# Verifica se não está roteando para redes públicas sem necessidade
if not any(ip in ipaddress.IPv4Network(rede) for rede in self.redes_privadas):
if ip_str != '0.0.0.0': # Permite rota padrão
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='ROTA_REDE_PUBLICA',
descricao=f'Rota para IP público {ip_str} - verificar necessidade',
severidade='MÉDIA',
sugestao='Confirme se rota para rede pública é necessária'
))
except ipaddress.AddressValueError:
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='IP_INVALIDO',
descricao=f'Endereço IP inválido: {ip_str}',
severidade='CRÍTICA',
sugestao='Corrija o formato do endereço IP'
))
# Verifica rota padrão
if '0.0.0.0 0.0.0.0' in linha and 'ip route' in linha.lower():
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='ROTA_PADRAO_DETECTADA',
descricao='Rota padrão configurada - verificar se é intencional',
severidade='BAIXA',
sugestao='Confirme se rota padrão é necessária para este dispositivo'
))
return erros
def _validar_interface(self, linha: str, numero_linha: int) -> List[ErroConfiguracao]:
"""Valida configurações de interface"""
erros = []
linha_lower = linha.lower()
# Verifica interfaces em shutdown
if 'shutdown' in linha_lower and not linha_lower.startswith('no shutdown'):
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='INTERFACE_SHUTDOWN',
descricao='Interface configurada como shutdown',
severidade='MÉDIA',
sugestao='Verifique se interface deve estar ativa (use "no shutdown")'
))
# Verifica configuração de IP
if 'ip address' in linha_lower:
# Extrai IP e máscara
match = re.search(r'ip address\s+(\d+\.\d+\.\d+\.\d+)\s+(\d+\.\d+\.\d+\.\d+)', linha_lower)
if match:
ip_str, mask_str = match.groups()
try:
ip = ipaddress.IPv4Address(ip_str)
mask = ipaddress.IPv4Address(mask_str)
# Verifica se IP está em rede privada
if not any(ip in ipaddress.IPv4Network(rede) for rede in self.redes_privadas):
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='IP_PUBLICO_INTERFACE',
descricao=f'Interface com IP público {ip_str}',
severidade='ALTA',
sugestao='Verifique se IP público na interface é intencional'
))
except ipaddress.AddressValueError:
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='IP_INVALIDO_INTERFACE',
descricao='IP ou máscara inválidos na interface',
severidade='CRÍTICA',
sugestao='Corrija o formato do IP e máscara'
))
return erros
def _validar_linha(self, linha: str, numero_linha: int, contexto: str) -> List[ErroConfiguracao]:
"""Validações gerais para qualquer linha"""
erros = []
# Verifica senhas em texto claro
if 'password' in linha.lower() and 'enable secret' not in linha.lower():
if not any(keyword in linha.lower() for keyword in ['encrypted', 'md5', 'sha']):
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='SENHA_TEXTO_CLARO',
descricao='Senha configurada em texto claro',
severidade='CRÍTICA',
sugestao='Use "enable secret" ou configure criptografia de senhas'
))
# Verifica comandos depreciados
comandos_depreciados = ['telnet', 'rsh', 'rcp']
for comando in comandos_depreciados:
if comando in linha.lower():
erros.append(ErroConfiguracao(
linha=numero_linha,
tipo='COMANDO_DEPRECIADO',
descricao=f'Comando depreciado detectado: {comando}',
severidade='ALTA',
sugestao=f'Substitua {comando} por alternativa segura (SSH, SCP)'
))
return erros
# Demonstração prática
def demonstrar_validacao_config_rede():
validador = ValidadorConfiguracaoRede()
# Configuração de exemplo (com vários problemas intencionais)
config_exemplo = '''!
! Configuração de Switch - Exemplo com Problemas
!
vlan 1
name default
!
vlan 4095
name vlan_problema
!
vlan 50
name producao
!
interface FastEthernet0/1
switchport mode access
switchport access vlan 50
no shutdown
!
interface FastEthernet0/2
ip address 8.8.8.8 255.255.255.0
shutdown
!
access-list 100 permit ip any any
access-list 101 permit tcp any any eq 22
access-list 102 permit tcp any any eq 23
!
ip route 0.0.0.0 0.0.0.0 192.168.1.1
ip route 8.8.8.0 255.255.255.0 10.0.0.1
!
enable password minhasenha
username admin password 123456
!
'''
# Salva configuração em arquivo temporário
import tempfile
import os
with tempfile.NamedTemporaryFile(mode='w', suffix='.cfg', delete=False) as f:
f.write(config_exemplo)
arquivo_config = f.name
try:
print("🔍 Validação de Configuração de Rede\n")
print("📄 Analisando configuração...")
erros = validador.validar_arquivo_configuracao(arquivo_config)
if erros:
# Agrupa erros por severidade
erros_por_severidade = {}
for erro in erros:
if erro.severidade not in erros_por_severidade:
erros_por_severidade[erro.severidade] = []
erros_por_severidade[erro.severidade].append(erro)
# Exibe erros ordenados por severidade
ordem_severidade = ['CRÍTICA', 'ALTA', 'MÉDIA', 'BAIXA']
for severidade in ordem_severidade:
if severidade in erros_por_severidade:
print(f"\n🚨 Problemas de Severidade {severidade}:")
for erro in erros_por_severidade[severidade]:
print(f" Linha {erro.linha}: {erro.tipo}")
print(f" {erro.descricao}")
print(f" 💡 {erro.sugestao}")
print()
# Estatísticas
total_erros = len(erros)
criticos = len([e for e in erros if e.severidade == 'CRÍTICA'])
altos = len([e for e in erros if e.severidade == 'ALTA'])
print(f"📊 Resumo da Análise:")
print(f" Total de problemas encontrados: {total_erros}")
print(f" Problemas críticos: {criticos}")
print(f" Problemas de alta severidade: {altos}")
if criticos > 0:
print(f" ⚠️ AÇÃO NECESSÁRIA: Corrija problemas críticos antes do deploy!")
else:
print("✅ Configuração validada com sucesso - nenhum problema encontrado!")
finally:
# Remove arquivo temporário
os.unlink(arquivo_config)
# Executa demonstração
demonstrar_validacao_config_rede()class ValidadorConfiguracaoRede {
constructor() {
this.vlansPermitidas = Array.from({length: 4085}, (_, i) => i + 10); // 10-4094
this.redesPrivadas = ['10.0.0.0/8', '172.16.0.0/12', '192.168.0.0/16'];
this.portasProibidas = [22, 23, 135, 139, 445];
}
validarConfiguracao(configuracao, nomeArquivo = 'config.cfg') {
const linhas = configuracao.split('\n');
const erros = [];
let contextoAtual = null;
linhas.forEach((linha, indice) => {
const numeroLinha = indice + 1;
const linhaLimpa = linha.trim();
if (!linhaLimpa || linhaLimpa.startsWith('!')) {
return; // Pula linhas vazias e comentários
}
// Detecta contexto
contextoAtual = this._detectarContexto(linhaLimpa, contextoAtual);
// Validações específicas por contexto
switch (contextoAtual) {
case 'vlan':
erros.push(...this._validarVlan(linhaLimpa, numeroLinha));
break;
case 'acl':
erros.push(...this._validarAcl(linhaLimpa, numeroLinha));
break;
case 'route':
erros.push(...this._validarRota(linhaLimpa, numeroLinha));
break;
case 'interface':
erros.push(...this._validarInterface(linhaLimpa, numeroLinha));
break;
}
// Validações gerais
erros.push(...this._validarLinha(linhaLimpa, numeroLinha));
});
return erros;
}
_detectarContexto(linha, contextoAnterior) {
const linhaLower = linha.toLowerCase();
if (linhaLower.startsWith('vlan ')) return 'vlan';
if (linhaLower.startsWith('access-list')) return 'acl';
if (linhaLower.startsWith('ip route')) return 'route';
if (linhaLower.startsWith('interface')) return 'interface';
if (['exit', 'end'].includes(linhaLower) || linhaLower.startsWith('!')) return null;
return contextoAnterior;
}
_validarVlan(linha, numeroLinha) {
const erros = [];
const match = linha.toLowerCase().match(/vlan\s+(\d+)/);
if (match) {
const vlanId = parseInt(match[1]);
// Verifica range permitido
if (!this.vlansPermitidas.includes(vlanId)) {
erros.push({
linha: numeroLinha,
tipo: 'VLAN_FORA_RANGE',
descricao: `VLAN ${vlanId} fora do range permitido (10-4094)`,
severidade: 'ALTA',
sugestao: 'Use VLAN entre 10 e 4094'
});
}
// Verifica VLANs reservadas
if ([1, 1002, 1003, 1004, 1005].includes(vlanId)) {
erros.push({
linha: numeroLinha,
tipo: 'VLAN_RESERVADA',
descricao: `VLAN ${vlanId} é reservada do sistema`,
severidade: 'CRÍTICA',
sugestao: 'Use uma VLAN não reservada'
});
}
}
return erros;
}
_validarAcl(linha, numeroLinha) {
const erros = [];
const linhaLower = linha.toLowerCase();
// Verifica regras muito permissivas
if (linhaLower.includes('permit') && linhaLower.includes('any any')) {
erros.push({
linha: numeroLinha,
tipo: 'ACL_MUITO_PERMISSIVA',
descricao: 'Regra ACL muito permissiva (any any)',
severidade: 'CRÍTICA',
sugestao: 'Restrinja origem e destino'
});
}
// Verifica portas perigosas
for (const porta of this.portasProibidas) {
if (linhaLower.includes(`eq ${porta}`) && linhaLower.includes('permit')) {
erros.push({
linha: numeroLinha,
tipo: 'PORTA_INSEGURA',
descricao: `ACL permite porta insegura ${porta}`,
severidade: 'ALTA',
sugestao: `Bloqueie acesso à porta ${porta}`
});
}
}
return erros;
}
_validarRota(linha, numeroLinha) {
const erros = [];
// Verifica rota padrão
if (linha.includes('0.0.0.0 0.0.0.0')) {
erros.push({
linha: numeroLinha,
tipo: 'ROTA_PADRAO_DETECTADA',
descricao: 'Rota padrão configurada',
severidade: 'BAIXA',
sugestao: 'Confirme se rota padrão é necessária'
});
}
// Valida formato de IPs
const ips = linha.match(/\b(?:\d{1,3}\.){3}\d{1,3}\b/g);
if (ips) {
for (const ip of ips) {
if (!this._validarFormatoIP(ip)) {
erros.push({
linha: numeroLinha,
tipo: 'IP_INVALIDO',
descricao: `IP inválido: ${ip}`,
severidade: 'CRÍTICA',
sugestao: 'Corrija o formato do IP'
});
}
}
}
return erros;
}
_validarInterface(linha, numeroLinha) {
const erros = [];
const linhaLower = linha.toLowerCase();
// Verifica shutdown
if (linhaLower.includes('shutdown') && !linhaLower.includes('no shutdown')) {
erros.push({
linha: numeroLinha,
tipo: 'INTERFACE_SHUTDOWN',
descricao: 'Interface em shutdown',
severidade: 'MÉDIA',
sugestao: 'Verifique se interface deve estar ativa'
});
}
// Verifica IP público em interface
if (linhaLower.includes('ip address')) {
const match = linhaLower.match(/ip address\s+(\d+\.\d+\.\d+\.\d+)/);
if (match) {
const ip = match[1];
if (!this._isIPPrivado(ip)) {
erros.push({
linha: numeroLinha,
tipo: 'IP_PUBLICO_INTERFACE',
descricao: `Interface com IP público: ${ip}`,
severidade: 'ALTA',
sugestao: 'Verifique se IP público é intencional'
});
}
}
}
return erros;
}
_validarLinha(linha, numeroLinha) {
const erros = [];
const linhaLower = linha.toLowerCase();
// Verifica senhas em texto claro
if (linhaLower.includes('password') && !linhaLower.includes('enable secret')) {
if (!['encrypted', 'md5', 'sha'].some(enc => linhaLower.includes(enc))) {
erros.push({
linha: numeroLinha,
tipo: 'SENHA_TEXTO_CLARO',
descricao: 'Senha em texto claro detectada',
severidade: 'CRÍTICA',
sugestao: 'Use "enable secret" ou configure criptografia'
});
}
}
// Verifica comandos depreciados
const comandosDepreciados = ['telnet', 'rsh', 'rcp'];
for (const comando of comandosDepreciados) {
if (linhaLower.includes(comando)) {
erros.push({
linha: numeroLinha,
tipo: 'COMANDO_DEPRECIADO',
descricao: `Comando depreciado: ${comando}`,
severidade: 'ALTA',
sugestao: `Substitua por alternativa segura (SSH/SCP)`
});
}
}
return erros;
}
_validarFormatoIP(ip) {
const partes = ip.split('.');
if (partes.length !== 4) return false;
return partes.every(parte => {
const num = parseInt(parte);
return !isNaN(num) && num >= 0 && num <= 255;
});
}
_isIPPrivado(ip) {
const [a, b] = ip.split('.').map(Number);
// 10.0.0.0/8
if (a === 10) return true;
// 172.16.0.0/12
if (a === 172 && b >= 16 && b <= 31) return true;
// 192.168.0.0/16
if (a === 192 && b === 168) return true;
return false;
}
}
// Demonstração
function demonstrarValidacaoRede() {
const validador = new ValidadorConfiguracaoRede();
const configExemplo = `!
! Configuração com problemas intencionais
!
vlan 1
name default
!
vlan 4095
name problema
!
interface FastEthernet0/1
ip address 8.8.8.8 255.255.255.0
shutdown
!
access-list 100 permit ip any any
access-list 101 permit tcp any any eq 23
!
ip route 0.0.0.0 0.0.0.0 192.168.1.1
!
enable password senhafraca
username admin password 123
!`;
console.log("🔍 Validação de Configuração de Rede\n");
const erros = validador.validarConfiguracao(configExemplo);
if (erros.length > 0) {
// Agrupa por severidade
const porSeveridade = {};
erros.forEach(erro => {
if (!porSeveridade[erro.severidade]) {
porSeveridade[erro.severidade] = [];
}
porSeveridade[erro.severidade].push(erro);
});
// Exibe ordenado por severidade
['CRÍTICA', 'ALTA', 'MÉDIA', 'BAIXA'].forEach(severidade => {
if (porSeveridade[severidade]) {
console.log(`\n🚨 Problemas ${severidade}:`);
porSeveridade[severidade].forEach(erro => {
console.log(` Linha ${erro.linha}: ${erro.tipo}`);
console.log(` ${erro.descricao}`);
console.log(` 💡 ${erro.sugestao}\n`);
});
}
});
const criticos = (porSeveridade['CRÍTICA'] || []).length;
console.log(`📊 Total: ${erros.length} problemas (${criticos} críticos)`);
if (criticos > 0) {
console.log("⚠️ AÇÃO NECESSÁRIA: Corrija problemas críticos!");
}
} else {
console.log("✅ Configuração válida!");
}
}
demonstrarValidacaoRede();🎯 Reflexões sobre os Casos Reais Apresentados
Os quatro casos reais que exploramos demonstram a versatilidade e poder prático dos autômatos finitos não-determinísticos em cenários do mundo real. Cada exemplo ilustra como as técnicas fundamentais de construção que estudamos se aplicam a problemas computacionais genuínos que você encontrará em sua carreira profissional.
Lições Fundamentais dos Casos Práticos
Decomposição Modular em Ação: O caso de validação de email mostrou como quebrar um problema complexo (formato de email completo) em subproblemas gerenciáveis (parte local, domínio, extensão). Esta abordagem é fundamental não apenas para AFNs, mas para resolução de problemas computacionais em geral.
Construção por Antecipação Revelada: Os casos de análise de logs e detecção de vulnerabilidades demonstraram como AFNs podem “apostar” em múltiplos padrões simultaneamente, detectando ameaças de segurança que seriam difíceis de capturar com abordagens puramente determinísticas.
Padrão de Confirmação Múltipla Materializado: O analisador de código-fonte mostrou como manter múltiplas hipóteses sobre contexto até que evidência suficiente confirme ou refute cada possibilidade. Esta técnica é essencial para análise de linguagens com sintaxe ambígua ou dependente de contexto.
Escalabilidade e Eficiência: O validador de configurações de rede demonstrou como AFNs podem processar grandes volumes de dados estruturados, mantendo múltiplos contextos de validação simultaneamente sem explosão combinatória incontrolável.
🛠️ Estratégias Práticas de Design
Comece com casos simples: Identifique os casos mais básicos do padrão que você quer reconhecer e construa estados para tratá-los explicitamente.
Use não-determinismo para alternativas: Quando múltiplas possibilidades existem, use transições não-determinísticas em vez de tentar codificar toda a lógica de decisão em estados separados.
Mantenha estrutura modular: Organize seu AFN em “módulos” conceituais que tratam diferentes aspectos do reconhecimento, conectando-os com transições não-determinísticas apropriadas.
Teste incrementalmente: Construa seu AFN gradualmente, testando cada componente antes de adicionar complexidade adicional.
Estratégias Práticas de Design com Casos Aplicados à Disciplina
Para dominar verdadeiramente o design de AFNs no contexto de compiladores e linguagens formais, você precisa ir além da teoria e mergulhar em situações práticas onde as estratégias de design se materializam em soluções elegantes para problemas reais de análise léxica e sintática. Vamos explorar casos específicos da nossa disciplina onde cada estratégia revela seu valor prático no desenvolvimento de compiladores.
Estratégia 1: Comece com Casos Simples 🎯
Caso Real: Design Incremental de Analisador Léxico para Linguagem de Programação Educacional
Imagine que seu grupo está desenvolvendo um compilador para uma linguagem de programação educacional que será usada em cursos introdutórios. Em vez de tentar especificar todos os tokens complexos de uma vez, você aplicará a estratégia de começar com casos simples e evoluir incrementalmente.
O Desafio Prático: Sua linguagem precisa suportar expressões aritméticas, declarações de variáveis, estruturas de controle, e funções. Começar com toda essa complexidade simultaneamente levaria a AFNs confusos e difíceis de debugar.
Implementação da Estratégia:
graph TB
subgraph "Evolução Incremental do Analisador Léxico"
A["Operadores Básicos"] --> B[Números Inteiros]
B --> C[Identificadores Simples]
C --> D[Palavras-chave]
D --> E[Números Decimais]
E --> F[Strings e Comentários]
A1["+ - * /"] --> B1[123, 456]
B1 --> C1[abc, var1]
C1 --> D1[if, while, int]
D1 --> E1[3.14, 2.5e10]
E1 --> F1["hello", // comentário]
end
style A fill:#e3f2fd
style B fill:#e8f5e8
style C fill:#fff3e0
style D fill:#f3e5f5
style E fill:#ffebee
style F fill:#f0f4c3
class AnalisadorLexicoEducacional:
def __init__(self):
# Começamos com casos simples e evoluímos incrementalmente
self.afn_atual = self._construir_operadores_basicos()
self.historico_evolucao = []
self.tokens_reconhecidos = set()
def _construir_operadores_basicos(self):
"""
FASE 1: Apenas operadores aritméticos básicos
Tokens: +, -, *, /, =, (, )
"""
estados = {'inicio', 'operador_simples', 'token_aceito'}
transicoes = {
('inicio', '+'): {'operador_simples'},
('inicio', '-'): {'operador_simples'},
('inicio', '*'): {'operador_simples'},
('inicio', '/'): {'operador_simples'},
('inicio', '='): {'operador_simples'},
('inicio', '('): {'operador_simples'},
('inicio', ')'): {'operador_simples'},
('operador_simples', 'FIM'): {'token_aceito'}
}
afn = AFN(estados, set(), transicoes, 'inicio', {'token_aceito'})
self.historico_evolucao.append('Fase 1: Operadores aritméticos básicos (+, -, *, /, =, parênteses)')
self.tokens_reconhecidos.update(['PLUS', 'MINUS', 'MULTIPLY', 'DIVIDE', 'ASSIGN', 'LPAREN', 'RPAREN'])
return afn
def evoluir_para_numeros_inteiros(self):
"""
FASE 2: Adiciona reconhecimento de números inteiros
Tokens: 123, 456, 0, 999
"""
estados_anteriores = self.afn_atual.estados.copy()
novos_estados = {'digito', 'numero_completo', 'mais_digitos'}
estados = estados_anteriores.union(novos_estados)
transicoes_anteriores = self.afn_atual.transicoes.copy()
novas_transicoes = {
('inicio', 'DIGITO'): {'digito'},
('digito', 'DIGITO'): {'mais_digitos'},
('digito', 'FIM'): {'numero_completo'},
('mais_digitos', 'DIGITO'): {'mais_digitos'},
('mais_digitos', 'FIM'): {'numero_completo'}
}
transicoes_anteriores.update(novas_transicoes)
self.afn_atual = AFN(estados, set(), transicoes_anteriores, 'inicio',
self.afn_atual.estados_finais.union({'numero_completo'}))
self.historico_evolucao.append('Fase 2: Números inteiros (0-9)+')
self.tokens_reconhecidos.add('INTEGER')
def evoluir_para_identificadores(self):
"""
FASE 3: Adiciona identificadores simples
Tokens: abc, var1, temp, x
"""
estados_anteriores = self.afn_atual.estados.copy()
novos_estados = {'letra_inicial', 'id_continuacao', 'identificador_completo'}
estados = estados_anteriores.union(novos_estados)
transicoes_anteriores = self.afn_atual.transicoes.copy()
novas_transicoes = {
('inicio', 'LETRA'): {'letra_inicial'},
('letra_inicial', 'LETRA'): {'id_continuacao'},
('letra_inicial', 'DIGITO'): {'id_continuacao'},
('letra_inicial', 'FIM'): {'identificador_completo'},
('id_continuacao', 'LETRA'): {'id_continuacao'},
('id_continuacao', 'DIGITO'): {'id_continuacao'},
('id_continuacao', 'FIM'): {'identificador_completo'}
}
transicoes_anteriores.update(novas_transicoes)
self.afn_atual = AFN(estados, set(), transicoes_anteriores, 'inicio',
self.afn_atual.estados_finais.union({'identificador_completo'}))
self.historico_evolucao.append('Fase 3: Identificadores simples (letra seguida de letras/dígitos)')
self.tokens_reconhecidos.add('IDENTIFIER')
def evoluir_para_palavras_chave(self):
"""
FASE 4: Distingue palavras-chave de identificadores
Palavras-chave: if, else, while, for, int, float, return
"""
estados_anteriores = self.afn_atual.estados.copy()
# Estados específicos para cada palavra-chave (não-determinismo útil aqui)
novos_estados = {
'if_i', 'if_f', 'if_completo',
'else_e', 'else_l', 'else_s', 'else_e2', 'else_completo',
'while_w', 'while_h', 'while_i', 'while_l', 'while_e', 'while_completo',
'int_i', 'int_n', 'int_t', 'int_completo',
'return_r', 'return_e', 'return_t', 'return_u', 'return_r2', 'return_n', 'return_completo'
}
estados = estados_anteriores.union(novos_estados)
transicoes_anteriores = self.afn_atual.transicoes.copy()
# Palavras-chave como caminhos não-determinísticos paralelos aos identificadores
novas_transicoes = {
# "if" - usa não-determinismo para tentar tanto identificador quanto palavra-chave
('inicio', 'i'): {'letra_inicial', 'if_i'}, # Não-determinismo!
('if_i', 'f'): {'if_f'},
('if_f', 'FIM'): {'if_completo'},
# "else"
('inicio', 'e'): {'letra_inicial', 'else_e'}, # Não-determinismo!
('else_e', 'l'): {'else_l'},
('else_l', 's'): {'else_s'},
('else_s', 'e'): {'else_e2'},
('else_e2', 'FIM'): {'else_completo'},
# "while"
('inicio', 'w'): {'letra_inicial', 'while_w'}, # Não-determinismo!
('while_w', 'h'): {'while_h'},
('while_h', 'i'): {'while_i'},
('while_i', 'l'): {'while_l'},
('while_l', 'e'): {'while_e'},
('while_e', 'FIM'): {'while_completo'},
# "int"
('inicio', 'i'): {'letra_inicial', 'if_i', 'int_i'}, # Triplo não-determinismo!
('int_i', 'n'): {'int_n'},
('int_n', 't'): {'int_t'},
('int_t', 'FIM'): {'int_completo'},
# "return"
('inicio', 'r'): {'letra_inicial', 'return_r'}, # Não-determinismo!
('return_r', 'e'): {'return_e'},
('return_e', 't'): {'return_t'},
('return_t', 'u'): {'return_u'},
('return_u', 'r'): {'return_r2'},
('return_r2', 'n'): {'return_n'},
('return_n', 'FIM'): {'return_completo'}
}
transicoes_anteriores.update(novas_transicoes)
estados_finais = self.afn_atual.estados_finais.union({
'if_completo', 'else_completo', 'while_completo',
'int_completo', 'return_completo'
})
self.afn_atual = AFN(estados, set(), transicoes_anteriores, 'inicio', estados_finais)
self.historico_evolucao.append('Fase 4: Palavras-chave usando não-determinismo (if, else, while, int, return)')
self.tokens_reconhecidos.update(['IF', 'ELSE', 'WHILE', 'INT', 'RETURN'])
def evoluir_para_numeros_decimais(self):
"""
FASE 5: Números decimais e notação científica
Tokens: 3.14, 2.5e10, 1.0e-5
"""
estados_anteriores = self.afn_atual.estados.copy()
novos_estados = {
'ponto_decimal', 'digitos_decimais', 'e_cientifico',
'sinal_expoente', 'digitos_expoente', 'numero_decimal_completo'
}
estados = estados_anteriores.union(novos_estados)
transicoes_anteriores = self.afn_atual.transicoes.copy()
novas_transicoes = {
# A partir de número inteiro, pode ter ponto decimal
('mais_digitos', '.'): {'ponto_decimal'},
('numero_completo', '.'): {'ponto_decimal'}, # Conflito resolvido por não-determinismo
# Dígitos após o ponto
('ponto_decimal', 'DIGITO'): {'digitos_decimais'},
('digitos_decimais', 'DIGITO'): {'digitos_decimais'},
('digitos_decimais', 'FIM'): {'numero_decimal_completo'},
# Notação científica
('digitos_decimais', 'e'): {'e_cientifico'},
('digitos_decimais', 'E'): {'e_cientifico'},
('e_cientifico', '+'): {'sinal_expoente'},
('e_cientifico', '-'): {'sinal_expoente'},
('e_cientifico', 'DIGITO'): {'digitos_expoente'},
('sinal_expoente', 'DIGITO'): {'digitos_expoente'},
('digitos_expoente', 'DIGITO'): {'digitos_expoente'},
('digitos_expoente', 'FIM'): {'numero_decimal_completo'}
}
transicoes_anteriores.update(novas_transicoes)
self.afn_atual = AFN(estados, set(), transicoes_anteriores, 'inicio',
self.afn_atual.estados_finais.union({'numero_decimal_completo'}))
self.historico_evolucao.append('Fase 5: Números decimais e notação científica (3.14, 2.5e10)')
self.tokens_reconhecidos.update(['FLOAT', 'SCIENTIFIC'])
def evoluir_para_strings_e_comentarios(self):
"""
FASE 6: Strings e comentários de linha
Tokens: "hello world", // comentário até fim da linha
"""
estados_anteriores = self.afn_atual.estados.copy()
novos_estados = {
'aspas_abertas', 'caractere_string', 'escape_char', 'string_completa',
'barra1', 'barra2', 'comentario_linha', 'comentario_completo'
}
estados = estados_anteriores.union(novos_estados)
transicoes_anteriores = self.afn_atual.transicoes.copy()
novas_transicoes = {
# Strings
('inicio', '"'): {'aspas_abertas'},
('aspas_abertas', 'CHAR'): {'caractere_string'},
('aspas_abertas', '\\'): {'escape_char'},
('caractere_string', 'CHAR'): {'caractere_string'},
('caractere_string', '\\'): {'escape_char'},
('caractere_string', '"'): {'string_completa'},
('escape_char', 'CHAR'): {'caractere_string'}, # Qualquer char após escape
('string_completa', 'FIM'): {'token_aceito'},
# Comentários
('inicio', '/'): {'operador_simples', 'barra1'}, # Não-determinismo: pode ser divisão ou comentário
('barra1', '/'): {'barra2'},
('barra2', 'CHAR'): {'comentario_linha'},
('comentario_linha', 'CHAR'): {'comentario_linha'},
('comentario_linha', 'NEWLINE'): {'comentario_completo'},
('comentario_completo', 'FIM'): {'token_aceito'}
}
transicoes_anteriores.update(novas_transicoes)
estados_finais = self.afn_atual.estados_finais.union({'string_completa', 'comentario_completo'})
self.afn_atual = AFN(estados, set(), transicoes_anteriores, 'inicio', estados_finais)
self.historico_evolucao.append('Fase 6: Strings com escape e comentários de linha')
self.tokens_reconhecidos.update(['STRING', 'COMMENT'])
def demonstrar_evolucao_incremental(self):
"""Demonstra como a abordagem incremental simplifica o design"""
print("🎯 Estratégia: Comece com Casos Simples")
print("=" * 60)
print("📚 Contexto: Analisador Léxico para Linguagem Educacional")
print()
# Testa cada fase
casos_teste = [
# Fase 1: Operadores
(["+ - * / = ( )"], "operadores básicos"),
# Fase 2: Números
(["123", "456", "0"], "números inteiros"),
# Fase 3: Identificadores
(["abc", "var1", "temp"], "identificadores"),
# Fase 4: Palavras-chave
(["if", "else", "while", "int", "return"], "palavras-chave"),
# Fase 5: Decimais
(["3.14", "2.5e10", "1.0e-5"], "números decimais"),
# Fase 6: Strings e comentários
(['"hello world"', "// comentário"], "strings e comentários")
]
fases_metodos = [
self._construir_operadores_basicos,
self.evoluir_para_numeros_inteiros,
self.evoluir_para_identificadores,
self.evoluir_para_palavras_chave,
self.evoluir_para_numeros_decimais,
self.evoluir_para_strings_e_comentarios
]
for i, ((casos, descricao), metodo) in enumerate(zip(casos_teste, fases_metodos)):
if i > 0: # Pula o primeiro (já construído)
metodo()
print(f"📝 FASE {i+1}: Testando {descricao}")
for caso in casos:
if isinstance(caso, list):
for subcaso in caso:
resultado = self._simular_reconhecimento(subcaso)
print(f" {subcaso}: {'✓' if resultado else '✗'}")
else:
resultado = self._simular_reconhecimento(caso)
print(f" {caso}: {'✓' if resultado else '✗'}")
print()
# Mostra evolução
print("📈 Histórico de Evolução:")
for i, fase in enumerate(self.historico_evolucao, 1):
print(f" {i}. {fase}")
print(f"\n🎯 Tokens Reconhecidos: {sorted(self.tokens_reconhecidos)}")
print(f"\n💡 Benefícios da Abordagem Incremental para Compiladores:")
print(f" • Cada tipo de token testado isoladamente")
print(f" • Conflitos de ambiguidade detectados e resolvidos cedo")
print(f" • AFN final é mais robusto e bem estruturado")
print(f" • Desenvolvimento paralelo de parser pode começar antes")
print(f" • Debugging é muito mais simples")
# Mostra exemplo de conflito resolvido por não-determinismo
print(f"\n🌊 Exemplo de Não-Determinismo Resolvendo Conflitos:")
print(f" • Palavra 'int': pode ser identificador OU palavra-chave")
print(f" • Símbolo '/': pode ser divisão OU início de comentário")
print(f" • AFN explora ambas possibilidades simultaneamente")
print(f" • Contexto posterior resolve a ambiguidade")
def _simular_reconhecimento(self, entrada):
"""Simula processamento de uma entrada pelo AFN atual"""
# Simplificação: na implementação real seria mais sofisticado
tokens_esperados = {
'+': 'PLUS', '-': 'MINUS', '*': 'MULTIPLY', '/': 'DIVIDE',
'=': 'ASSIGN', '(': 'LPAREN', ')': 'RPAREN',
'123': 'INTEGER', '456': 'INTEGER', '0': 'INTEGER',
'abc': 'IDENTIFIER', 'var1': 'IDENTIFIER', 'temp': 'IDENTIFIER',
'if': 'IF', 'else': 'ELSE', 'while': 'WHILE', 'int': 'INT', 'return': 'RETURN',
'3.14': 'FLOAT', '2.5e10': 'SCIENTIFIC', '1.0e-5': 'SCIENTIFIC',
'"hello world"': 'STRING', '// comentário': 'COMMENT'
}
return entrada in tokens_esperados and tokens_esperados[entrada] in self.tokens_reconhecidos
# Demonstração da estratégia
print("🔬 Demonstração: Estratégia de Design Incremental para Compiladores\n")
analisador = AnalisadorLexicoEducacional()
analisador.demonstrar_evolucao_incremental()class AnalisadorLexicoEducacional {
constructor() {
this.afnAtual = this._construirOperadoresBasicos();
this.historicoEvolucao = [];
this.tokensReconhecidos = new Set();
}
_construirOperadoresBasicos() {
const transicoes = new Map([
['inicio,+', ['operador_simples']],
['inicio,-', ['operador_simples']],
['inicio,*', ['operador_simples']],
['inicio,/', ['operador_simples']],
['inicio,=', ['operador_simples']],
['inicio,(', ['operador_simples']],
['inicio,)', ['operador_simples']],
['operador_simples,FIM', ['token_aceito']]
]);
this.historicoEvolucao.push('Fase 1: Operadores aritméticos básicos');
this.tokensReconhecidos = new Set(['PLUS', 'MINUS', 'MULTIPLY', 'DIVIDE', 'ASSIGN', 'LPAREN', 'RPAREN']);
return new AFN(
['inicio', 'operador_simples', 'token_aceito'],
['+', '-', '*', '/', '=', '(', ')', 'FIM'],
transicoes,
'inicio',
['token_aceito']
);
}
evoluirParaNumerosInteiros() {
const novasTransicoes = new Map([
...this.afnAtual.transicoes,
['inicio,DIGITO', ['digito']],
['digito,DIGITO', ['mais_digitos']],
['digito,FIM', ['numero_completo']],
['mais_digitos,DIGITO', ['mais_digitos']],
['mais_digitos,FIM', ['numero_completo']]
]);
this.afnAtual = new AFN(
[...this.afnAtual.estados, 'digito', 'numero_completo', 'mais_digitos'],
[...this.afnAtual.alfabeto, 'DIGITO'],
novasTransicoes,
'inicio',
[...this.afnAtual.estadosFinais, 'numero_completo']
);
this.historicoEvolucao.push('Fase 2: Números inteiros');
this.tokensReconhecidos.add('INTEGER');
}
evoluirParaIdentificadores() {
const novasTransicoes = new Map([
...this.afnAtual.transicoes,
['inicio,LETRA', ['letra_inicial']],
['letra_inicial,LETRA', ['id_continuacao']],
['letra_inicial,DIGITO', ['id_continuacao']],
['letra_inicial,FIM', ['identificador_completo']],
['id_continuacao,LETRA', ['id_continuacao']],
['id_continuacao,DIGITO', ['id_continuacao']],
['id_continuacao,FIM', ['identificador_completo']]
]);
this.afnAtual = new AFN(
[...this.afnAtual.estados, 'letra_inicial', 'id_continuacao', 'identificador_completo'],
[...this.afnAtual.alfabeto, 'LETRA'],
novasTransicoes,
'inicio',
[...this.afnAtual.estadosFinais, 'identificador_completo']
);
this.historicoEvolucao.push('Fase 3: Identificadores simples');
this.tokensReconhecidos.add('IDENTIFIER');
}
evoluirParaPalavrasChave() {
// Implementação das palavras-chave usando não-determinismo
const novasTransicoes = new Map([
...this.afnAtual.transicoes,
// "if" - não-determinismo: pode ser identificador ou palavra-chave
['inicio,i', ['letra_inicial', 'if_i']],
['if_i,f', ['if_f']],
['if_f,FIM', ['if_completo']],
// "else"
['inicio,e', ['letra_inicial', 'else_e']],
['else_e,l', ['else_l']],
['else_l,s', ['else_s']],
['else_s,e', ['else_e2']],
['else_e2,FIM', ['else_completo']],
// "while"
['inicio,w', ['letra_inicial', 'while_w']],
['while_w,h', ['while_h']],
['while_h,i', ['while_i']],
['while_i,l', ['while_l']],
['while_l,e', ['while_e']],
['while_e,FIM', ['while_completo']]
]);
const novosEstados = [
'if_i', 'if_f', 'if_completo',
'else_e', 'else_l', 'else_s', 'else_e2', 'else_completo',
'while_w', 'while_h', 'while_i', 'while_l', 'while_e', 'while_completo'
];
this.afnAtual = new AFN(
[...this.afnAtual.estados, ...novosEstados],
[...this.afnAtual.alfabeto, 'i', 'f', 'e', 'l', 's', 'w', 'h'],
novasTransicoes,
'inicio',
[...this.afnAtual.estadosFinais, 'if_completo', 'else_completo', 'while_completo']
);
this.historicoEvolucao.push('Fase 4: Palavras-chave com não-determinismo');
this.tokensReconhecidos.add('IF');
this.tokensReconhecidos.add('ELSE');
this.tokensReconhecidos.add('WHILE');
}
demonstrarEvolucaoIncremental() {
console.log("🎯 Estratégia: Comece com Casos Simples");
console.log("=".repeat(60));
console.log("📚 Contexto: Analisador Léxico para Linguagem Educacional\n");
const casosTeste = [
{tokens: ['+', '-', '*', '/'], descricao: 'operadores básicos'},
{tokens: ['123', '456', '0'], descricao: 'números inteiros'},
{tokens: ['abc', 'var1', 'temp'], descricao: 'identificadores'},
{tokens: ['if', 'else', 'while'], descricao: 'palavras-chave'}
];
const metodos = [
() => {}, // Já construído
() => this.evoluirParaNumerosInteiros(),
() => this.evoluirParaIdentificadores(),
() => this.evoluirParaPalavrasChave()
];
casosTeste.forEach((caso, i) => {
if (i > 0) metodos[i]();
console.log(`📝 FASE ${i + 1}: Testando ${caso.descricao}`);
caso.tokens.forEach(token => {
const resultado = this._simularReconhecimento(token);
console.log(` ${token}: ${resultado ? '✓' : '✗'}`);
});
console.log();
});
console.log("📈 Histórico de Evolução:");
this.historicoEvolucao.forEach((fase, i) => {
console.log(` ${i + 1}. ${fase}`);
});
console.log(`\n🎯 Tokens Reconhecidos: ${Array.from(this.tokensReconhecidos).sort()}`);
console.log("\n💡 Benefícios da Abordagem Incremental:");
console.log(" • Cada tipo de token testado isoladamente");
console.log(" • Conflitos detectados e resolvidos cedo");
console.log(" • AFN final mais robusto");
console.log(" • Desenvolvimento paralelo possível");
console.log("\n🌊 Não-Determinismo Resolvendo Conflitos:");
console.log(" • 'if': identificador OU palavra-chave");
console.log(" • AFN explora ambas possibilidades");
console.log(" • Contexto resolve ambiguidade");
}
_simularReconhecimento(entrada) {
const tokensEsperados = {
'+': 'PLUS', '-': 'MINUS', '*': 'MULTIPLY', '/': 'DIVIDE',
'=': 'ASSIGN', '(': 'LPAREN', ')': 'RPAREN',
'123': 'INTEGER', '456': 'INTEGER', '0': 'INTEGER',
'abc': 'IDENTIFIER', 'var1': 'IDENTIFIER', 'temp': 'IDENTIFIER',
'if': 'IF', 'else': 'ELSE', 'while': 'WHILE'
};
return entrada in tokensEsperados &&
this.tokensReconhecidos.has(tokensEsperados[entrada]);
}
}
// Demonstração
console.log("🔬 Demonstração: Estratégia de Design Incremental\n");
const analisador = new AnalisadorLexicoEducacional();
analisador.demonstrarEvolucaoIncremental();Estratégia 2: Use Não-Determinismo para Alternativas 🌊
Caso Real: Reconhecimento de Literais em Linguagens de Programação
Imagine que seu grupo está implementando o analisador léxico para uma linguagem que suporta múltiplas notações para o mesmo tipo de literal. Por exemplo, números podem ser expressos em decimal, hexadecimal, octal, ou binário. Strings podem usar aspas simples ou duplas. Caracteres podem usar diferentes sequências de escape.
O Desafio Prático: Um AFD tradicional precisaria de estados separados para cada notação, levando a uma explosão de estados e transições difíceis de manter. O não-determinismo permite que o AFN “tente” múltiplas interpretações simultaneamente.
graph TB
subgraph "AFN para Múltiplas Notações de Literais"
A[Início] --> B{Primeiro Caractere}
B -->|"0"| C[Zero Inicial]
B -->|"1-9"| D[Decimal Normal]
B -->|"'"| E[String Simples]
B -->|"''"| F[String Dupla]
C -->|"x"| G[Hexadecimal]
C -->|"b"| H[Binário]
C -->|"0-7"| I[Octal]
C -->|"."| J[Decimal 0.x]
D --> K[Mais Dígitos]
K --> L[Número Completo]
G --> M[Dígitos Hex]
H --> N[Dígitos Bin]
I --> O[Dígitos Oct]
E --> P[Chars Simples]
F --> Q[Chars Duplas]
P --> R[String Terminada]
Q --> R
end
style A fill:#e3f2fd
style R fill:#90EE90
style L fill:#90EE90
class ReconhecedorLiterais {
late AFN afnLiterais;
Map<String, String> tiposReconhecidos = {};
ReconhecedorLiterais() {
afnLiterais = _construirAFNLiteraisCompleto();
}
AFN _construirAFNLiteraisCompleto() {
/*
Este AFN usa não-determinismo extensivamente para reconhecer
múltiplas notações de literais simultaneamente:
- Números: decimal, hex (0x...), octal (0...), binário (0b...)
- Strings: aspas simples e duplas
- Caracteres: com sequências de escape
*/
final estados = <String>{
'inicio',
// Estados para números
'zero_inicial', 'decimal_normal', 'mais_digitos',
'hex_x', 'hex_digitos', 'bin_b', 'bin_digitos', 'oct_digitos',
'ponto_decimal', 'digitos_fracao', 'numero_completo',
// Estados para strings
'aspas_simples', 'aspas_duplas', 'char_simples', 'char_duplas',
'escape_simples', 'escape_duplas', 'string_completa',
// Estados para caracteres especiais
'char_literal', 'escape_char', 'char_completo'
};
final transicoes = <String, Set<String>>{
// INÍCIO - Não-determinismo para diferentes tipos de literais
'inicio,0': {'zero_inicial'}, // Pode ser decimal, octal, hex, bin
'inicio,1': {'decimal_normal'}, // Decimal 1-9
'inicio,2': {'decimal_normal'}, 'inicio,3': {'decimal_normal'},
'inicio,4': {'decimal_normal'}, 'inicio,5': {'decimal_normal'},
'inicio,6': {'decimal_normal'}, 'inicio,7': {'decimal_normal'},
'inicio,8': {'decimal_normal'}, 'inicio,9': {'decimal_normal'},
'inicio,\'': {'aspas_simples'}, // String com aspas simples
'inicio,"': {'aspas_duplas'}, // String com aspas duplas
// ZERO INICIAL - Múltiplas possibilidades não-determinísticas
'zero_inicial,x': {'hex_x'}, // 0x... hexadecimal
'zero_inicial,X': {'hex_x'}, // 0X... hexadecimal
'zero_inicial,b': {'bin_b'}, // 0b... binário
'zero_inicial,B': {'bin_b'}, // 0B... binário
'zero_inicial,0': {'oct_digitos'}, // 00... octal
'zero_inicial,1': {'oct_digitos'}, 'zero_inicial,2': {'oct_digitos'},
'zero_inicial,3': {'oct_digitos'}, 'zero_inicial,4': {'oct_digitos'},
'zero_inicial,5': {'oct_digitos'}, 'zero_inicial,6': {'oct_digitos'},
'zero_inicial,7': {'oct_digitos'}, // Octal 0-7
'zero_inicial,.': {'ponto_decimal'}, // 0.xxx decimal
'zero_inicial,FIM': {'numero_completo'}, // Apenas "0"
// HEXADECIMAL
'hex_x,0': {'hex_digitos'}, 'hex_x,1': {'hex_digitos'},
'hex_x,2': {'hex_digitos'}, 'hex_x,3': {'hex_digitos'},
'hex_x,4': {'hex_digitos'}, 'hex_x,5': {'hex_digitos'},
'hex_x,6': {'hex_digitos'}, 'hex_x,7': {'hex_digitos'},
'hex_x,8': {'hex_digitos'}, 'hex_x,9': {'hex_digitos'},
'hex_x,a': {'hex_digitos'}, 'hex_x,b': {'hex_digitos'},
'hex_x,c': {'hex_digitos'}, 'hex_x,d': {'hex_digitos'},
'hex_x,e': {'hex_digitos'}, 'hex_x,f': {'hex_digitos'},
'hex_x,A': {'hex_digitos'}, 'hex_x,B': {'hex_digitos'},
'hex_x,C': {'hex_digitos'}, 'hex_x,D': {'hex_digitos'},
'hex_x,E': {'hex_digitos'}, 'hex_x,F': {'hex_digitos'},
'hex_digitos,0': {'hex_digitos'}, 'hex_digitos,1': {'hex_digitos'},
'hex_digitos,2': {'hex_digitos'}, 'hex_digitos,3': {'hex_digitos'},
'hex_digitos,4': {'hex_digitos'}, 'hex_digitos,5': {'hex_digitos'},
'hex_digitos,6': {'hex_digitos'}, 'hex_digitos,7': {'hex_digitos'},
'hex_digitos,8': {'hex_digitos'}, 'hex_digitos,9': {'hex_digitos'},
'hex_digitos,a': {'hex_digitos'}, 'hex_digitos,b': {'hex_digitos'},
'hex_digitos,c': {'hex_digitos'}, 'hex_digitos,d': {'hex_digitos'},
'hex_digitos,e': {'hex_digitos'}, 'hex_digitos,f': {'hex_digitos'},
'hex_digitos,A': {'hex_digitos'}, 'hex_digitos,B': {'hex_digitos'},
'hex_digitos,C': {'hex_digitos'}, 'hex_digitos,D': {'hex_digitos'},
'hex_digitos,E': {'hex_digitos'}, 'hex_digitos,F': {'hex_digitos'},
'hex_digitos,FIM': {'numero_completo'},
// BINÁRIO
'bin_b,0': {'bin_digitos'}, 'bin_b,1': {'bin_digitos'},
'bin_digitos,0': {'bin_digitos'}, 'bin_digitos,1': {'bin_digitos'},
'bin_digitos,FIM': {'numero_completo'},
// OCTAL
'oct_digitos,0': {'oct_digitos'}, 'oct_digitos,1': {'oct_digitos'},
'oct_digitos,2': {'oct_digitos'}, 'oct_digitos,3': {'oct_digitos'},
'oct_digitos,4': {'oct_digitos'}, 'oct_digitos,5': {'oct_digitos'},
'oct_digitos,6': {'oct_digitos'}, 'oct_digitos,7': {'oct_digitos'},
'oct_digitos,FIM': {'numero_completo'},
// DECIMAL NORMAL
'decimal_normal,0': {'mais_digitos'}, 'decimal_normal,1': {'mais_digitos'},
'decimal_normal,2': {'mais_digitos'}, 'decimal_normal,3': {'mais_digitos'},
'decimal_normal,4': {'mais_digitos'}, 'decimal_normal,5': {'mais_digitos'},
'decimal_normal,6': {'mais_digitos'}, 'decimal_normal,7': {'mais_digitos'},
'decimal_normal,8': {'mais_digitos'}, 'decimal_normal,9': {'mais_digitos'},
'decimal_normal,.': {'ponto_decimal'},
'decimal_normal,FIM': {'numero_completo'},
'mais_digitos,0': {'mais_digitos'}, 'mais_digitos,1': {'mais_digitos'},
'mais_digitos,2': {'mais_digitos'}, 'mais_digitos,3': {'mais_digitos'},
'mais_digitos,4': {'mais_digitos'}, 'mais_digitos,5': {'mais_digitos'},
'mais_digitos,6': {'mais_digitos'}, 'mais_digitos,7': {'mais_digitos'},
'mais_digitos,8': {'mais_digitos'}, 'mais_digitos,9': {'mais_digitos'},
'mais_digitos,.': {'ponto_decimal'},
'mais_digitos,FIM': {'numero_completo'},
// DECIMAIS COM PONTO
'ponto_decimal,0': {'digitos_fracao'}, 'ponto_decimal,1': {'digitos_fracao'},
'ponto_decimal,2': {'digitos_fracao'}, 'ponto_decimal,3': {'digitos_fracao'},
'ponto_decimal,4': {'digitos_fracao'}, 'ponto_decimal,5': {'digitos_fracao'},
'ponto_decimal,6': {'digitos_fracao'}, 'ponto_decimal,7': {'digitos_fracao'},
'ponto_decimal,8': {'digitos_fracao'}, 'ponto_decimal,9': {'digitos_fracao'},
'digitos_fracao,0': {'digitos_fracao'}, 'digitos_fracao,1': {'digitos_fracao'},
'digitos_fracao,2': {'digitos_fracao'}, 'digitos_fracao,3': {'digitos_fracao'},
'digitos_fracao,4': {'digitos_fracao'}, 'digitos_fracao,5': {'digitos_fracao'},
'digitos_fracao,6': {'digitos_fracao'}, 'digitos_fracao,7': {'digitos_fracao'},
'digitos_fracao,8': {'digitos_fracao'}, 'digitos_fracao,9': {'digitos_fracao'},
'digitos_fracao,FIM': {'numero_completo'},
// STRINGS COM ASPAS SIMPLES
'aspas_simples,CHAR': {'char_simples'},
'aspas_simples,\\': {'escape_simples'},
'char_simples,CHAR': {'char_simples'},
'char_simples,\\': {'escape_simples'},
'char_simples,\'': {'string_completa'},
'escape_simples,CHAR': {'char_simples'}, // Qualquer char após escape
// STRINGS COM ASPAS DUPLAS
'aspas_duplas,CHAR': {'char_duplas'},
'aspas_duplas,\\': {'escape_duplas'},
'char_duplas,CHAR': {'char_duplas'},
'char_duplas,\\': {'escape_duplas'},
'char_duplas,"': {'string_completa'},
'escape_duplas,CHAR': {'char_duplas'},
// FINALIZAÇÕES
'string_completa,FIM': {'numero_completo'}, // Reutiliza estado final
};
return AFN(
estados: estados,
alfabeto: <String>{}, // Será preenchido dinamicamente
transicoes: transicoes,
estadoInicial: 'inicio',
estadosFinais: {'numero_completo'}
);
}
ResultadoReconhecimento analisarLiteral(String entrada) {
/*
Demonstra como não-determinismo resolve ambiguidades:
- "0123" pode ser octal OU decimal com zero à esquerda
- "0x" pode ser hex incompleto OU dois tokens separados
- Strings podem ter aspas simples ou duplas
*/
print("🌊 Analisando '$entrada' com não-determinismo...");
final tokens = _tokenizarEntrada(entrada);
var estadosAtivos = <String>{'inicio'};
final rastreamento = <String>[];
rastreamento.add("Estados iniciais: $estadosAtivos");
for (final token in tokens) {
final novosEstados = <String>{};
for (final estado in estadosAtivos) {
final chave = '$estado,$token';
if (afnLiterais.transicoes.containsKey(chave)) {
novosEstados.addAll(afnLiterais.transicoes[chave]!);
}
}
estadosAtivos = novosEstados;
rastreamento.add("Após '$token': $estadosAtivos");
if (estadosAtivos.isEmpty) {
return ResultadoReconhecimento(
aceito: false,
tipoToken: 'ERRO',
detalhes: 'Nenhum estado ativo após token: $token',
rastreamento: rastreamento
);
}
}
// Verifica se algum estado final está ativo
final estadosFinaisAtivos = estadosAtivos
.where((estado) => afnLiterais.estadosFinais.contains(estado))
.toSet();
if (estadosFinaisAtivos.isNotEmpty) {
final tipoDetectado = _determinarTipoLiteral(entrada, estadosAtivos);
return ResultadoReconhecimento(
aceito: true,
tipoToken: tipoDetectado,
detalhes: 'Literal reconhecido com sucesso',
rastreamento: rastreamento,
estadosFinaisAtivos: estadosFinaisAtivos
);
}
return ResultadoReconhecimento(
aceito: false,
tipoToken: 'INCOMPLETO',
detalhes: 'Estados ativos: $estadosAtivos, mas nenhum é final',
rastreamento: rastreamento
);
}
String _determinarTipoLiteral(String entrada, Set<String> estadosAtivos) {
// Determina tipo baseado no formato da entrada
if (entrada.startsWith('0x') || entrada.startsWith('0X')) {
return 'HEXADECIMAL';
} else if (entrada.startsWith('0b') || entrada.startsWith('0B')) {
return 'BINARIO';
} else if (entrada.startsWith('0') && entrada.length > 1 &&
!entrada.contains('.') && entrada.split('').every((c) => '01234567'.contains(c))) {
return 'OCTAL';
} else if (entrada.contains('.')) {
return 'DECIMAL_FRACAO';
} else if (entrada.startsWith('"') || entrada.startsWith("'")) {
return 'STRING';
} else {
return 'DECIMAL_INTEIRO';
}
}
List<String> _tokenizarEntrada(String entrada) {
final tokens = <String>[];
for (int i = 0; i < entrada.length; i++) {
final char = entrada[i];
tokens.add(char);
}
tokens.add('FIM');
return tokens;
}
void demonstrarNaoDeterminismo() {
print("🎯 Estratégia: Use Não-Determinismo para Alternativas");
print("=" * 60);
print("📚 Contexto: Reconhecimento de Múltiplas Notações de Literais\n");
final casosAmbiguos = [
'0123', // Pode ser octal ou decimal
'0x1A', // Hexadecimal
'0b101', // Binário
'3.14', // Decimal com ponto
'"hello"', // String com aspas duplas
"'world'", // String com aspas simples
'0', // Apenas zero
'42' // Decimal simples
];
for (final caso in casosAmbiguos) {
print("🧪 Testando literal: $caso");
final resultado = analisarLiteral(caso);
print(" Resultado: ${resultado.aceito ? '✓' : '✗'} ${resultado.tipoToken}");
print(" Detalhes: ${resultado.detalhes}");
if (resultado.rastreamento.length > 2) {
print(" Evolução dos estados:");
for (final passo in resultado.rastreamento.take(3)) {
print(" $passo");
}
if (resultado.rastreamento.length > 3) {
print(" ... (${resultado.rastreamento.length - 3} passos adicionais)");
}
}
if (resultado.estadosFinaisAtivos != null && resultado.estadosFinaisAtivos!.isNotEmpty) {
print(" Estados finais ativos: ${resultado.estadosFinaisAtivos}");
}
print("");
}
print("💡 Benefícios do Não-Determinismo para Literais:");
print(" • Explora múltiplas interpretações simultaneamente");
print(" • Resolve ambiguidades naturalmente");
print(" • Evita explosão de estados em AFD");
print(" • Facilita adição de novos formatos");
print(" • Mantém especificação clara e modular");
print("\n🌊 Exemplos de Não-Determinismo em Ação:");
print(" • '0123': AFN testa tanto octal quanto decimal");
print(" • '0x': Começa caminho hex, mas pode falhar e tentar outros");
print(" • Aspas: AFN aceita tanto simples quanto duplas");
print(" • Escape: \\n, \\t, \\' todos tratados uniformemente");
}
}
class ResultadoReconhecimento {
final bool aceito;
final String tipoToken;
final String detalhes;
final List<String> rastreamento;
final Set<String>? estadosFinaisAtivos;
ResultadoReconhecimento({
required this.aceito,
required this.tipoToken,
required this.detalhes,
required this.rastreamento,
this.estadosFinaisAtivos,
});
}
// Demonstração
void main() {
print("🔬 Demonstração: Não-Determinismo para Alternativas\n");
final reconhecedor = ReconhecedorLiterais();
reconhecedor.demonstrarNaoDeterminismo();
}#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <string>
#include <sstream>
class ReconhecedorLiterais {
private:
std::unordered_map<std::string, std::unordered_set<std::string>> transicoes;
std::unordered_set<std::string> estadosFinais;
std::unordered_map<std::string, std::string> tiposReconhecidos;
public:
ReconhecedorLiterais() {
construirAFNLiteraisCompleto();
}
void construirAFNLiteraisCompleto() {
/*
AFN que usa não-determinismo extensivamente para reconhecer
múltiplas notações de literais simultaneamente:
- Números: decimal, hex (0x...), octal (0...), binário (0b...)
- Strings: aspas simples e duplas
- Caracteres com sequências de escape
*/
// INÍCIO - Não-determinismo para diferentes tipos de literais
transicoes["inicio,0"].insert("zero_inicial");
for (char c = '1'; c <= '9'; c++) {
std::string key = "inicio," + std::string(1, c);
transicoes[key].insert("decimal_normal");
}
transicoes["inicio,'"].insert("aspas_simples");
transicoes["inicio,\""].insert("aspas_duplas");
// ZERO INICIAL - Múltiplas possibilidades não-determinísticas
transicoes["zero_inicial,x"].insert("hex_x");
transicoes["zero_inicial,X"].insert("hex_x");
transicoes["zero_inicial,b"].insert("bin_b");
transicoes["zero_inicial,B"].insert("bin_b");
// Octal (0-7 após zero inicial)
for (char c = '0'; c <= '7'; c++) {
std::string key = "zero_inicial," + std::string(1, c);
transicoes[key].insert("oct_digitos");
}
transicoes["zero_inicial,."].insert("ponto_decimal");
transicoes["zero_inicial,FIM"].insert("numero_completo");
// HEXADECIMAL
std::string hexChars = "0123456789abcdefABCDEF";
for (char c : hexChars) {
std::string key = "hex_x," + std::string(1, c);
transicoes[key].insert("hex_digitos");
key = "hex_digitos," + std::string(1, c);
transicoes[key].insert("hex_digitos");
}
transicoes["hex_digitos,FIM"].insert("numero_completo");
// BINÁRIO
transicoes["bin_b,0"].insert("bin_digitos");
transicoes["bin_b,1"].insert("bin_digitos");
transicoes["bin_digitos,0"].insert("bin_digitos");
transicoes["bin_digitos,1"].insert("bin_digitos");
transicoes["bin_digitos,FIM"].insert("numero_completo");
// OCTAL
for (char c = '0'; c <= '7'; c++) {
std::string key = "oct_digitos," + std::string(1, c);
transicoes[key].insert("oct_digitos");
}
transicoes["oct_digitos,FIM"].insert("numero_completo");
// DECIMAL NORMAL
for (char c = '0'; c <= '9'; c++) {
std::string key = "decimal_normal," + std::string(1, c);
transicoes[key].insert("mais_digitos");
key = "mais_digitos," + std::string(1, c);
transicoes[key].insert("mais_digitos");
}
transicoes["decimal_normal,."].insert("ponto_decimal");
transicoes["decimal_normal,FIM"].insert("numero_completo");
transicoes["mais_digitos,."].insert("ponto_decimal");
transicoes["mais_digitos,FIM"].insert("numero_completo");
// DECIMAIS COM PONTO
for (char c = '0'; c <= '9'; c++) {
std::string key = "ponto_decimal," + std::string(1, c);
transicoes[key].insert("digitos_fracao");
key = "digitos_fracao," + std::string(1, c);
transicoes[key].insert("digitos_fracao");
}
transicoes["digitos_fracao,FIM"].insert("numero_completo");
// STRINGS COM ASPAS SIMPLES
transicoes["aspas_simples,CHAR"].insert("char_simples");
transicoes["aspas_simples,\\"].insert("escape_simples");
transicoes["char_simples,CHAR"].insert("char_simples");
transicoes["char_simples,\\"].insert("escape_simples");
transicoes["char_simples,'"].insert("string_completa");
transicoes["escape_simples,CHAR"].insert("char_simples");
// STRINGS COM ASPAS DUPLAS
transicoes["aspas_duplas,CHAR"].insert("char_duplas");
transicoes["aspas_duplas,\\"].insert("escape_duplas");
transicoes["char_duplas,CHAR"].insert("char_duplas");
transicoes["char_duplas,\\"].insert("escape_duplas");
transicoes["char_duplas,\""].insert("string_completa");
transicoes["escape_duplas,CHAR"].insert("char_duplas");
// FINALIZAÇÕES
transicoes["string_completa,FIM"].insert("numero_completo");
// Estados finais
estadosFinais.insert("numero_completo");
}
struct ResultadoReconhecimento {
bool aceito;
std::string tipoToken;
std::string detalhes;
std::vector<std::string> rastreamento;
std::unordered_set<std::string> estadosFinaisAtivos;
};
ResultadoReconhecimento analisarLiteral(const std::string& entrada) {
/*
Demonstra como não-determinismo resolve ambiguidades:
- "0123" pode ser octal OU decimal com zero à esquerda
- "0x" pode ser hex incompleto OU dois tokens separados
- Strings podem ter aspas simples ou duplas
*/
std::cout << "🌊 Analisando '" << entrada << "' com não-determinismo...\n";
auto tokens = tokenizarEntrada(entrada);
std::unordered_set<std::string> estadosAtivos = {"inicio"};
std::vector<std::string> rastreamento;
rastreamento.push_back("Estados iniciais: {inicio}");
for (const auto& token : tokens) {
std::unordered_set<std::string> novosEstados;
for (const auto& estado : estadosAtivos) {
std::string chave = estado + "," + token;
if (transicoes.count(chave)) {
for (const auto& destino : transicoes[chave]) {
novosEstados.insert(destino);
}
}
}
estadosAtivos = novosEstados;
std::stringstream ss;
ss << "Após '" << token << "': {";
bool primeiro = true;
for (const auto& estado : estadosAtivos) {
if (!primeiro) ss << ", ";
ss << estado;
primeiro = false;
}
ss << "}";
rastreamento.push_back(ss.str());
if (estadosAtivos.empty()) {
return {
false,
"ERRO",
"Nenhum estado ativo após token: " + token,
rastreamento,
{}
};
}
}
// Verifica se algum estado final está ativo
std::unordered_set<std::string> estadosFinaisAtivos;
for (const auto& estado : estadosAtivos) {
if (estadosFinais.count(estado)) {
estadosFinaisAtivos.insert(estado);
}
}
if (!estadosFinaisAtivos.empty()) {
std::string tipoDetectado = determinarTipoLiteral(entrada, estadosAtivos);
return {
true,
tipoDetectado,
"Literal reconhecido com sucesso",
rastreamento,
estadosFinaisAtivos
};
}
return {
false,
"INCOMPLETO",
"Estados ativos mas nenhum é final",
rastreamento,
{}
};
}
std::string determinarTipoLiteral(const std::string& entrada,
const std::unordered_set<std::string>& estadosAtivos) {
// Determina tipo baseado no formato da entrada
if (entrada.substr(0, 2) == "0x" || entrada.substr(0, 2) == "0X") {
return "HEXADECIMAL";
} else if (entrada.substr(0, 2) == "0b" || entrada.substr(0, 2) == "0B") {
return "BINARIO";
} else if (entrada[0] == '0' && entrada.length() > 1 &&
entrada.find('.') == std::string::npos) {
// Verifica se todos são dígitos octais
bool todoOctal = true;
for (char c : entrada) {
if (c < '0' || c > '7') {
todoOctal = false;
break;
}
}
if (todoOctal) return "OCTAL";
} else if (entrada.find('.') != std::string::npos) {
return "DECIMAL_FRACAO";
} else if (entrada[0] == '"' || entrada[0] == '\'') {
return "STRING";
} else {
return "DECIMAL_INTEIRO";
}
}
std::vector<std::string> tokenizarEntrada(const std::string& entrada) {
std::vector<std::string> tokens;
for (char c : entrada) {
if (c == ' ' || c == '\t' || c == '\n') continue; // Pula espaços
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
(c >= '0' && c <= '9') || c == '_') {
tokens.push_back("CHAR");
} else {
tokens.push_back(std::string(1, c));
}
}
tokens.push_back("FIM");
return tokens;
}
void demonstrarNaoDeterminismo() {
std::cout << "🎯 Estratégia: Use Não-Determinismo para Alternativas\n";
std::cout << std::string(60, '=') << "\n";
std::cout << "📚 Contexto: Reconhecimento de Múltiplas Notações de Literais\n\n";
std::vector<std::string> casosAmbiguos = {
"0123", // Pode ser octal ou decimal
"0x1A", // Hexadecimal
"0b101", // Binário
"3.14", // Decimal com ponto
"\"hello\"", // String com aspas duplas
"'world'", // String com aspas simples
"0", // Apenas zero
"42" // Decimal simples
};
for (const auto& caso : casosAmbiguos) {
std::cout << "🧪 Testando literal: " << caso << "\n";
auto resultado = analisarLiteral(caso);
std::cout << " Resultado: " << (resultado.aceito ? "✓" : "✗")
<< " " << resultado.tipoToken << "\n";
std::cout << " Detalhes: " << resultado.detalhes << "\n";
if (resultado.rastreamento.size() > 2) {
std::cout << " Evolução dos estados:\n";
for (size_t i = 0; i < std::min(size_t(3), resultado.rastreamento.size()); i++) {
std::cout << " " << resultado.rastreamento[i] << "\n";
}
if (resultado.rastreamento.size() > 3) {
std::cout << " ... (" << (resultado.rastreamento.size() - 3)
<< " passos adicionais)\n";
}
}
if (!resultado.estadosFinaisAtivos.empty()) {
std::cout << " Estados finais ativos: {";
bool primeiro = true;
for (const auto& estado : resultado.estadosFinaisAtivos) {
if (!primeiro) std::cout << ", ";
std::cout << estado;
primeiro = false;
}
std::cout << "}\n";
}
std::cout << "\n";
}
std::cout << "💡 Benefícios do Não-Determinismo para Literais:\n";
std::cout << " • Explora múltiplas interpretações simultaneamente\n";
std::cout << " • Resolve ambiguidades naturalmente\n";
std::cout << " • Evita explosão de estados em AFD\n";
std::cout << " • Facilita adição de novos formatos\n";
std::cout << " • Mantém especificação clara e modular\n";
std::cout << "\n🌊 Exemplos de Não-Determinismo em Ação:\n";
std::cout << " • '0123': AFN testa tanto octal quanto decimal\n";
std::cout << " • '0x': Começa caminho hex, mas pode falhar e tentar outros\n";
std::cout << " • Aspas: AFN aceita tanto simples quanto duplas\n";
std::cout << " • Escape: \\n, \\t, \\' todos tratados uniformemente\n";
}
};
// Demonstração
int main() {
std::cout << "🔬 Demonstração: Não-Determinismo para Alternativas\n\n";
ReconhecedorLiterais reconhecedor;
reconhecedor.demonstrarNaoDeterminismo();
return 0;
}Estratégia 3: Mantenha Estrutura Modular 🏗️
Caso Real: Analisador Sintático para Expressões Matemáticas com Precedência
Imagine que seu grupo está implementando um analisador sintático para expressões matemáticas complexas que devem respeitar precedência de operadores, associatividade, e suportar funções matemáticas. A estratégia modular permite construir AFNs separados para cada componente e combiná-los elegantemente.
O Desafio Prático: Expressões como sin(x + 2) * cos(y^2) envolvem múltiplos níveis: identificadores, números, operadores, funções, parênteses. Um design monolítico seria impossível de manter e estender.
graph TB
subgraph "Arquitetura Modular para Expressões"
A[AFN Números] --> D[AFN Combinado]
B[AFN Identificadores] --> D
C[AFN Operadores] --> D
E[AFN Funções] --> D
F[AFN Parênteses] --> D
D --> G[AFN Expressão Simples]
G --> H[AFN Precedência]
H --> I[AFN Expressão Completa]
end
subgraph "Módulos Independentes"
J[Módulo Números<br/>123, 3.14, 2e5]
K[Módulo IDs<br/>x, var, temp]
L[Módulo Ops<br/>+, -, *, /, ^]
M[Módulo Funcs<br/>sin, cos, log]
end
style D fill:#e8f5e8
style I fill:#90EE90
class AnalisadorExpressoesModular {
// Módulos independentes - cada um é um AFN especializado
late AFN moduloNumeros;
late AFN moduloIdentificadores;
late AFN moduloOperadores;
late AFN moduloFuncoes;
late AFN moduloParenteses;
// AFN combinado final
late AFN afnExpressaoCompleta;
Map<String, int> precedenciaOperadores = {
'+': 1, '-': 1,
'*': 2, '/': 2,
'^': 3,
'sin': 4, 'cos': 4, 'log': 4, 'sqrt': 4
};
AnalisadorExpressoesModular() {
_construirModulosIndependentes();
_combinarModulos();
}
void _construirModulosIndependentes() {
/*
ESTRATÉGIA MODULAR: Cada componente é desenvolvido e testado
independentemente antes da integração
*/
// MÓDULO 1: Números (inteiros, decimais, científicos)
moduloNumeros = _construirModuloNumeros();
// MÓDULO 2: Identificadores (variáveis)
moduloIdentificadores = _construirModuloIdentificadores();
// MÓDULO 3: Operadores aritméticos
moduloOperadores = _construirModuloOperadores();
// MÓDULO 4: Funções matemáticas
moduloFuncoes = _construirModuloFuncoes();
// MÓDULO 5: Parênteses e agrupamento
moduloParenteses = _construirModuloParenteses();
}
AFN _construirModuloNumeros() {
/*
Módulo especializado apenas em reconhecer números
Entrada: "123", "3.14", "2.5e10", ".5"
Saída: Token NUMERO
*/
final estados = <String>{
'num_inicio', 'digitos_int', 'ponto_decimal', 'digitos_frac',
'e_cientifico', 'sinal_exp', 'digitos_exp', 'numero_aceito'
};
final transicoes = <String, Set<String>>{
// Números inteiros
'num_inicio,DIGITO': {'digitos_int'},
'num_inicio,.': {'ponto_decimal'}, // .5 é válido
'digitos_int,DIGITO': {'digitos_int'},
'digitos_int,.': {'ponto_decimal'},
'digitos_int,FIM': {'numero_aceito'},
// Parte decimal
'ponto_decimal,DIGITO': {'digitos_frac'},
'digitos_frac,DIGITO': {'digitos_frac'},
'digitos_frac,e': {'e_cientifico'},
'digitos_frac,E': {'e_cientifico'},
'digitos_frac,FIM': {'numero_aceito'},
// Notação científica
'e_cientifico,+': {'sinal_exp'},
'e_cientifico,-': {'sinal_exp'},
'e_cientifico,DIGITO': {'digitos_exp'},
'sinal_exp,DIGITO': {'digitos_exp'},
'digitos_exp,DIGITO': {'digitos_exp'},
'digitos_exp,FIM': {'numero_aceito'},
};
return AFN(
estados: estados,
alfabeto: <String>{},
transicoes: transicoes,
estadoInicial: 'num_inicio',
estadosFinais: {'numero_aceito'}
);
}
AFN _construirModuloIdentificadores() {
/*
Módulo para identificadores e nomes de variáveis
Entrada: "x", "var1", "temperatura", "_temp"
Saída: Token IDENTIFICADOR
*/
final estados = <String>{
'id_inicio', 'letra_inicial', 'id_continuacao', 'id_aceito'
};
final transicoes = <String, Set<String>>{
'id_inicio,LETRA': {'letra_inicial'},
'id_inicio,_': {'letra_inicial'}, // Pode começar com underscore
'letra_inicial,LETRA': {'id_continuacao'},
'letra_inicial,DIGITO': {'id_continuacao'},
'letra_inicial,_': {'id_continuacao'},
'letra_inicial,FIM': {'id_aceito'},
'id_continuacao,LETRA': {'id_continuacao'},
'id_continuacao,DIGITO': {'id_continuacao'},
'id_continuacao,_': {'id_continuacao'},
'id_continuacao,FIM': {'id_aceito'}
};
return AFN(
estados: estados,
alfabeto: <String>{},
transicoes: transicoes,
estadoInicial: 'id_inicio',
estadosFinais: {'id_aceito'}
);
}
AFN _construirModuloOperadores() {
/*
Módulo para operadores aritméticos
Entrada: "+", "-", "*", "/", "^", "**"
Saída: Token OPERADOR
*/
final estados = <String>{
'op_inicio', 'op_simples', 'op_duplo', 'op_aceito'
};
final transicoes = <String, Set<String>>{
'op_inicio,+': {'op_simples'},
'op_inicio,-': {'op_simples'},
'op_inicio,*': {'op_simples', 'op_duplo'}, // * ou **
'op_inicio,/': {'op_simples'},
'op_inicio,^': {'op_simples'},
'op_inicio,=': {'op_simples'}, // Para atribuição
'op_simples,FIM': {'op_aceito'},
'op_duplo,*': {'op_aceito'}, // ** para potência
'op_duplo,=': {'op_aceito'}, // += -= *= /=
};
return AFN(
estados: estados,
alfabeto: <String>{},
transicoes: transicoes,
estadoInicial: 'op_inicio',
estadosFinais: {'op_aceito'}
);
}
AFN _construirModuloFuncoes() {
/*
Módulo para funções matemáticas predefinidas
Entrada: "sin", "cos", "log", "sqrt", "exp"
Saída: Token FUNCAO
*/
final estados = <String>{
'func_inicio',
// Estados para "sin"
'sin_s', 'sin_i', 'sin_n', 'sin_aceito',
// Estados para "cos"
'cos_c', 'cos_o', 'cos_s', 'cos_aceito',
// Estados para "log"
'log_l', 'log_o', 'log_g', 'log_aceito',
// Estados para "sqrt"
'sqrt_s', 'sqrt_q', 'sqrt_r', 'sqrt_t', 'sqrt_aceito'
};
final transicoes = <String, Set<String>>{
// Não-determinismo: 's' pode iniciar 'sin' ou 'sqrt'
'func_inicio,s': {'sin_s', 'sqrt_s'},
'func_inicio,c': {'cos_c'},
'func_inicio,l': {'log_l'},
// "sin"
'sin_s,i': {'sin_i'},
'sin_i,n': {'sin_n'},
'sin_n,FIM': {'sin_aceito'},
// "cos"
'cos_c,o': {'cos_o'},
'cos_o,s': {'cos_s'},
'cos_s,FIM': {'cos_aceito'},
// "log"
'log_l,o': {'log_o'},
'log_o,g': {'log_g'},
'log_g,FIM': {'log_aceito'},
// "sqrt"
'sqrt_s,q': {'sqrt_q'},
'sqrt_q,r': {'sqrt_r'},
'sqrt_r,t': {'sqrt_t'},
'sqrt_t,FIM': {'sqrt_aceito'}
};
return AFN(
estados: estados,
alfabeto: <String>{},
transicoes: transicoes,
estadoInicial: 'func_inicio',
estadosFinais: {'sin_aceito', 'cos_aceito', 'log_aceito', 'sqrt_aceito'}
);
}
AFN _construirModuloParenteses() {
/*
Módulo para parênteses e colchetes
Entrada: "(", ")", "[", "]"
Saída: Token PARENTESE
*/
final estados = <String>{'paren_inicio', 'paren_aceito'};
final transicoes = <String, Set<String>>{
'paren_inicio,(': {'paren_aceito'},
'paren_inicio,)': {'paren_aceito'},
'paren_inicio,[': {'paren_aceito'},
'paren_inicio,]': {'paren_aceito'}
};
return AFN(
estados: estados,
alfabeto: <String>{},
transicoes: transicoes,
estadoInicial: 'paren_inicio',
estadosFinais: {'paren_aceito'}
);
}
void _combinarModulos() {
/*
INTEGRAÇÃO MODULAR: Combina todos os módulos em um AFN unificado
usando não-determinismo para tentar todos os módulos simultaneamente
*/
final estadosCombinados = <String>{'expr_inicio'};
final transicoesCombinadasMap = <String, Set<String>>{};
final estadosFinaisCombinados = <String>{'token_reconhecido'};
// Adiciona estados de todos os módulos com prefixos únicos
for (final estado in moduloNumeros.estados) {
estadosCombinados.add('num_$estado');
}
for (final estado in moduloIdentificadores.estados) {
estadosCombinados.add('id_$estado');
}
for (final estado in moduloOperadores.estados) {
estadosCombinados.add('op_$estado');
}
for (final estado in moduloFuncoes.estados) {
estadosCombinados.add('func_$estado');
}
for (final estado in moduloParenteses.estados) {
estadosCombinados.add('paren_$estado');
}
// INÍCIO NÃO-DETERMINÍSTICO: tenta todos os módulos simultaneamente
transicoesCombinadasMap['expr_inicio,DIGITO'] = {
'num_${moduloNumeros.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,.'] = {
'num_${moduloNumeros.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,LETRA'] = {
'id_${moduloIdentificadores.estadoInicial}',
'func_${moduloFuncoes.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,_'] = {
'id_${moduloIdentificadores.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,+'] = {
'op_${moduloOperadores.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,-'] = {
'op_${moduloOperadores.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,*'] = {
'op_${moduloOperadores.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,/'] = {
'op_${moduloOperadores.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,^'] = {
'op_${moduloOperadores.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,('] = {
'paren_${moduloParenteses.estadoInicial}'
};
transicoesCombinadasMap['expr_inicio,)'] = {
'paren_${moduloParenteses.estadoInicial}'
};
// Copia transições de cada módulo com prefixos
_copiarTransicoesModulo(moduloNumeros, 'num_', transicoesCombinadasMap);
_copiarTransicoesModulo(moduloIdentificadores, 'id_', transicoesCombinadasMap);
_copiarTransicoesModulo(moduloOperadores, 'op_', transicoesCombinadasMap);
_copiarTransicoesModulo(moduloFuncoes, 'func_', transicoesCombinadasMap);
_copiarTransicoesModulo(moduloParenteses, 'paren_', transicoesCombinadasMap);
// Conecta estados finais de módulos ao estado final unificado
for (final estadoFinal in moduloNumeros.estadosFinais) {
transicoesCombinadasMap['num_$estadoFinal,FIM'] = {'token_reconhecido'};
}
for (final estadoFinal in moduloIdentificadores.estadosFinais) {
transicoesCombinadasMap['id_$estadoFinal,FIM'] = {'token_reconhecido'};
}
for (final estadoFinal in moduloOperadores.estadosFinais) {
transicoesCombinadasMap['op_$estadoFinal,FIM'] = {'token_reconhecido'};
}
for (final estadoFinal in moduloFuncoes.estadosFinais) {
transicoesCombinadasMap['func_$estadoFinal,FIM'] = {'token_reconhecido'};
}
for (final estadoFinal in moduloParenteses.estadosFinais) {
transicoesCombinadasMap['paren_$estadoFinal,FIM'] = {'token_reconhecido'};
}
afnExpressaoCompleta = AFN(
estados: estadosCombinados,
alfabeto: <String>{},
transicoes: transicoesCombinadasMap,
estadoInicial: 'expr_inicio',
estadosFinais: estadosFinaisCombinados
);
}
void _copiarTransicoesModulo(AFN modulo, String prefixo, Map<String, Set<String>> destino) {
for (final entrada in modulo.transicoes.entries) {
final chaveOriginal = entrada.key;
final estadosDestino = entrada.value;
final chaveNova = prefixo + chaveOriginal;
final estadosDestinoNovos = estadosDestino.map((e) => prefixo + e).toSet();
destino[chaveNova] = estadosDestinoNovos;
}
}
ResultadoAnaliseToken analisarToken(String token) {
/*
Demonstra como estrutura modular facilita:
- Debugging (pode testar cada módulo separadamente)
- Manutenção (mudanças em um módulo não afetam outros)
- Extensibilidade (novos tipos de token são novos módulos)
*/
print("🏗️ Analisando token '$token' com arquitetura modular...");
// Primeiro, testa cada módulo individualmente para debug
final resultadosModulos = <String, bool>{};
resultadosModulos['Números'] = _testarModulo(moduloNumeros, token);
resultadosModulos['Identificadores'] = _testarModulo(moduloIdentificadores, token);
resultadosModulos['Operadores'] = _testarModulo(moduloOperadores, token);
resultadosModulos['Funções'] = _testarModulo(moduloFuncoes, token);
resultadosModulos['Parênteses'] = _testarModulo(moduloParenteses, token);
// Depois testa o AFN combinado
final tokens = _tokenizarEntrada(token);
var estadosAtivos = <String>{'expr_inicio'};
final rastreamento = <String>[];
for (final t in tokens) {
final novosEstados = <String>{};
for (final estado in estadosAtivos) {
final chave = '$estado,$t';
if (afnExpressaoCompleta.transicoes.containsKey(chave)) {
novosEstados.addAll(afnExpressaoCompleta.transicoes[chave]!);
}
}
estadosAtivos = novosEstados;
rastreamento.add("Após '$t': ${estadosAtivos.length} estados ativos");
if (estadosAtivos.isEmpty) break;
}
final aceito = estadosAtivos.any((e) => afnExpressaoCompleta.estadosFinais.contains(e));
final tipoToken = _determinarTipoToken(token, resultadosModulos);
return ResultadoAnaliseToken(
token: token,
aceito: aceito,
tipoToken: tipoToken,
resultadosModulos: resultadosModulos,
rastreamento: rastreamento
);
}
bool _testarModulo(AFN modulo, String entrada) {
final tokens = _tokenizarEntrada(entrada);
var estadosAtivos = <String>{modulo.estadoInicial};
for (final token in tokens) {
final novosEstados = <String>{};
for (final estado in estadosAtivos) {
final chave = '$estado,$token';
if (modulo.transicoes.containsKey(chave)) {
novosEstados.addAll(modulo.transicoes[chave]!);
}
}
estadosAtivos = novosEstados;
if (estadosAtivos.isEmpty) return false;
}
return estadosAtivos.any((e) => modulo.estadosFinais.contains(e));
}
String _determinarTipoToken(String token, Map<String, bool> resultados) {
if (resultados['Números'] == true) return 'NUMERO';
if (resultados['Funções'] == true) return 'FUNCAO';
if (resultados['Identificadores'] == true) return 'IDENTIFICADOR';
if (resultados['Operadores'] == true) return 'OPERADOR';
if (resultados['Parênteses'] == true) return 'PARENTESE';
return 'DESCONHECIDO';
}
List<String> _tokenizarEntrada(String entrada) {
final tokens = <String>[];
for (int i = 0; i < entrada.length; i++) {
final char = entrada[i];
if (char >= '0' && char <= '9') {
tokens.add('DIGITO');
} else if ((char >= 'a' && char <= 'z') || (char >= 'A' && char <= 'Z')) {
tokens.add('LETRA');
} else {
tokens.add(char);
}
}
tokens.add('FIM');
return tokens;
}
void demonstrarEstrutulaModular() {
print("🎯 Estratégia: Mantenha Estrutura Modular");
print("=" * 60);
print("📚 Contexto: Analisador de Expressões Matemáticas\n");
final casosTest = [
'123', // Número
'3.14', // Decimal
'x', // Identificador
'sin', // Função
'+', // Operador
'**', // Operador duplo
'(', // Parêntese
'temp_var', // Identificador complexo
'2.5e10', // Científico
'cos' // Função
];
for (final caso in casosTest) {
print("🧪 Analisando: '$caso'");
final resultado = analisarToken(caso);
print(" Resultado: ${resultado.aceito ? '✓' : '✗'} ${resultado.tipoToken}");
print(" Módulos que aceitaram:");
for (final entrada in resultado.resultadosModulos.entries) {
if (entrada.value) {
print(" ✓ ${entrada.key}");
}
}
print(" Passos de processamento: ${resultado.rastreamento.length}");
print("");
}
print("💡 Benefícios da Estrutura Modular:");
print(" • Cada módulo pode ser desenvolvido independentemente");
print(" • Debugging é isolado por módulo");
print(" • Fácil adição de novos tipos de token");
print(" • Manutenção localizada (mudança em um módulo)");
print(" • Testabilidade aprimorada");
print(" • Reutilização de módulos em outros projetos");
print("\n🏗️ Arquitetura Modular em Ação:");
print(" • 5 módulos independentes especializados");
print(" • Integração não-determinística elegante");
print(" • Estados com prefixos evitam conflitos");
print(" • Debug por módulo + debug integrado");
}
}
class ResultadoAnaliseToken {
final String token;
final bool aceito;
final String tipoToken;
final Map<String, bool> resultadosModulos;
final List<String> rastreamento;
ResultadoAnaliseToken({
required this.token,
required this.aceito,
required this.tipoToken,
required this.resultadosModulos,
required this.rastreamento,
});
}
// Demonstração
void main() {
print("🔬 Demonstração: Estrutura Modular para Compiladores\n");
final analisador = AnalisadorExpressoesModular();
analisador.demonstrarEstrutulaModular();
}#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>
class AFN {
public:
std::unordered_set<std::string> estados;
std::unordered_map<std::string, std::unordered_set<std::string>> transicoes;
std::string estadoInicial;
std::unordered_set<std::string> estadosFinais;
AFN(const std::unordered_set<std::string>& est,
const std::unordered_map<std::string, std::unordered_set<std::string>>& trans,
const std::string& inicial,
const std::unordered_set<std::string>& finais)
: estados(est), transicoes(trans), estadoInicial(inicial), estadosFinais(finais) {}
};
class AnalisadorExpressoesModular {
private:
// Módulos independentes - cada um é um AFN especializado
AFN moduloNumeros;
AFN moduloIdentificadores;
AFN moduloOperadores;
AFN moduloFuncoes;
AFN moduloParenteses;
// AFN combinado final
AFN afnExpressaoCompleta;
std::unordered_map<std::string, int> precedenciaOperadores = {
{"+", 1}, {"-", 1},
{"*", 2}, {"/", 2},
{"^", 3},
{"sin", 4}, {"cos", 4}, {"log", 4}, {"sqrt", 4}
};
public:
AnalisadorExpressoesModular()
: moduloNumeros(construirModuloNumeros()),
moduloIdentificadores(construirModuloIdentificadores()),
moduloOperadores(construirModuloOperadores()),
moduloFuncoes(construirModuloFuncoes()),
moduloParenteses(construirModuloParenteses()),
afnExpressaoCompleta(combinarModulos()) {
}
AFN construirModuloNumeros() {
/*
Módulo especializado apenas em reconhecer números
Entrada: "123", "3.14", "2.5e10", ".5"
Saída: Token NUMERO
*/
std::unordered_set<std::string> estados = {
"num_inicio", "digitos_int", "ponto_decimal", "digitos_frac",
"e_cientifico", "sinal_exp", "digitos_exp", "numero_aceito"
};
std::unordered_map<std::string, std::unordered_set<std::string>> transicoes = {
// Números inteiros
{"num_inicio,DIGITO", {"digitos_int"}},
{"num_inicio,.", {"ponto_decimal"}}, // .5 é válido
{"digitos_int,DIGITO", {"digitos_int"}},
{"digitos_int,.", {"ponto_decimal"}},
{"digitos_int,FIM", {"numero_aceito"}},
// Parte decimal
{"ponto_decimal,DIGITO", {"digitos_frac"}},
{"digitos_frac,DIGITO", {"digitos_frac"}},
{"digitos_frac,e", {"e_cientifico"}},
{"digitos_frac,E", {"e_cientifico"}},
{"digitos_frac,FIM", {"numero_aceito"}},
// Notação científica
{"e_cientifico,+", {"sinal_exp"}},
{"e_cientifico,-", {"sinal_exp"}},
{"e_cientifico,DIGITO", {"digitos_exp"}},
{"sinal_exp,DIGITO", {"digitos_exp"}},
{"digitos_exp,DIGITO", {"digitos_exp"}},
{"digitos_exp,FIM", {"numero_aceito"}}
};
return AFN(estados, transicoes, "num_inicio", {"numero_aceito"});
}
AFN construirModuloIdentificadores() {
/*
Módulo para identificadores e nomes de variáveis
Entrada: "x", "var1", "temperatura", "_temp"
Saída: Token IDENTIFICADOR
*/
std::unordered_set<std::string> estados = {
"id_inicio", "letra_inicial", "id_continuacao", "id_aceito"
};
std::unordered_map<std::string, std::unordered_set<std::string>> transicoes = {
{"id_inicio,LETRA", {"letra_inicial"}},
{"id_inicio,_", {"letra_inicial"}}, // Pode começar com underscore
{"letra_inicial,LETRA", {"id_continuacao"}},
{"letra_inicial,DIGITO", {"id_continuacao"}},
{"letra_inicial,_", {"id_continuacao"}},
{"letra_inicial,FIM", {"id_aceito"}},
{"id_continuacao,LETRA", {"id_continuacao"}},
{"id_continuacao,DIGITO", {"id_continuacao"}},
{"id_continuacao,_", {"id_continuacao"}},
{"id_continuacao,FIM", {"id_aceito"}}
};
return AFN(estados, transicoes, "id_inicio", {"id_aceito"});
}
AFN construirModuloOperadores() {
/*
Módulo para operadores aritméticos
Entrada: "+", "-", "*", "/", "^", "**"
Saída: Token OPERADOR
*/
std::unordered_set<std::string> estados = {
"op_inicio", "op_simples", "op_duplo", "op_aceito"
};
std::unordered_map<std::string, std::unordered_set<std::string>> transicoes = {
{"op_inicio,+", {"op_simples"}},
{"op_inicio,-", {"op_simples"}},
{"op_inicio,*", {"op_simples", "op_duplo"}}, // * ou **
{"op_inicio,/", {"op_simples"}},
{"op_inicio,^", {"op_simples"}},
{"op_inicio,=", {"op_simples"}}, // Para atribuição
{"op_simples,FIM", {"op_aceito"}},
{"op_duplo,*", {"op_aceito"}}, // ** para potência
{"op_duplo,=", {"op_aceito"}} // += -= *= /=
};
return AFN(estados, transicoes, "op_inicio", {"op_aceito"});
}
AFN construirModuloFuncoes() {
/*
Módulo para funções matemáticas predefinidas
Entrada: "sin", "cos", "log", "sqrt", "exp"
Saída: Token FUNCAO
*/
std::unordered_set<std::string> estados = {
"func_inicio",
// Estados para "sin"
"sin_s", "sin_i", "sin_n", "sin_aceito",
// Estados para "cos"
"cos_c", "cos_o", "cos_s", "cos_aceito",
// Estados para "log"
"log_l", "log_o", "log_g", "log_aceito",
// Estados para "sqrt"
"sqrt_s", "sqrt_q", "sqrt_r", "sqrt_t", "sqrt_aceito"
};
std::unordered_map<std::string, std::unordered_set<std::string>> transicoes = {
// Não-determinismo: 's' pode iniciar 'sin' ou 'sqrt'
{"func_inicio,s", {"sin_s", "sqrt_s"}},
{"func_inicio,c", {"cos_c"}},
{"func_inicio,l", {"log_l"}},
// "sin"
{"sin_s,i", {"sin_i"}},
{"sin_i,n", {"sin_n"}},
{"sin_n,FIM", {"sin_aceito"}},
// "cos"
{"cos_c,o", {"cos_o"}},
{"cos_o,s", {"cos_s"}},
{"cos_s,FIM", {"cos_aceito"}},
// "log"
{"log_l,o", {"log_o"}},
{"log_o,g", {"log_g"}},
{"log_g,FIM", {"log_aceito"}},
// "sqrt"
{"sqrt_s,q", {"sqrt_q"}},
{"sqrt_q,r", {"sqrt_r"}},
{"sqrt_r,t", {"sqrt_t"}},
{"sqrt_t,FIM", {"sqrt_aceito"}}
};
std::unordered_set<std::string> estadosFinais = {
"sin_aceito", "cos_aceito", "log_aceito", "sqrt_aceito"
};
return AFN(estados, transicoes, "func_inicio", estadosFinais);
}
AFN construirModuloParenteses() {
/*
Módulo para parênteses e colchetes
Entrada: "(", ")", "[", "]"
Saída: Token PARENTESE
*/
std::unordered_set<std::string> estados = {"paren_inicio", "paren_aceito"};
std::unordered_map<std::string, std::unordered_set<std::string>> transicoes = {
{"paren_inicio,(", {"paren_aceito"}},
{"paren_inicio,)", {"paren_aceito"}},
{"paren_inicio,[", {"paren_aceito"}},
{"paren_inicio,]", {"paren_aceito"}}
};
return AFN(estados, transicoes, "paren_inicio", {"paren_aceito"});
}
AFN combinarModulos() {
/*
INTEGRAÇÃO MODULAR: Combina todos os módulos em um AFN unificado
usando não-determinismo para tentar todos os módulos simultaneamente
*/
std::unordered_set<std::string> estadosCombinados = {"expr_inicio"};
std::unordered_map<std::string, std::unordered_set<std::string>> transicoesCombinadas;
std::unordered_set<std::string> estadosFinaisCombinados = {"token_reconhecido"};
// Adiciona estados de todos os módulos com prefixos únicos
for (const auto& estado : moduloNumeros.estados) {
estadosCombinados.insert("num_" + estado);
}
for (const auto& estado : moduloIdentificadores.estados) {
estadosCombinados.insert("id_" + estado);
}
for (const auto& estado : moduloOperadores.estados) {
estadosCombinados.insert("op_" + estado);
}
for (const auto& estado : moduloFuncoes.estados) {
estadosCombinados.insert("func_" + estado);
}
for (const auto& estado : moduloParenteses.estados) {
estadosCombinados.insert("paren_" + estado);
}
// INÍCIO NÃO-DETERMINÍSTICO: tenta todos os módulos simultaneamente
transicoesCombinadas["expr_inicio,DIGITO"] = {"num_" + moduloNumeros.estadoInicial};
transicoesCombinadas["expr_inicio,."] = {"num_" + moduloNumeros.estadoInicial};
transicoesCombinadas["expr_inicio,LETRA"] = {
"id_" + moduloIdentificadores.estadoInicial,
"func_" + moduloFuncoes.estadoInicial
};
transicoesCombinadas["expr_inicio,_"] = {"id_" + moduloIdentificadores.estadoInicial};
transicoesCombinadas["expr_inicio,+"] = {"op_" + moduloOperadores.estadoInicial};
transicoesCombinadas["expr_inicio,-"] = {"op_" + moduloOperadores.estadoInicial};
transicoesCombinadas["expr_inicio,*"] = {"op_" + moduloOperadores.estadoInicial};
transicoesCombinadas["expr_inicio,/"] = {"op_" + moduloOperadores.estadoInicial};
transicoesCombinadas["expr_inicio,^"] = {"op_" + moduloOperadores.estadoInicial};
transicoesCombinadas["expr_inicio,("] = {"paren_" + moduloParenteses.estadoInicial};
transicoesCombinadas["expr_inicio,)"] = {"paren_" + moduloParenteses.estadoInicial};
// Copia transições de cada módulo com prefixos
copiarTransicoesModulo(moduloNumeros, "num_", transicoesCombinadas);
copiarTransicoesModulo(moduloIdentificadores, "id_", transicoesCombinadas);
copiarTransicoesModulo(moduloOperadores, "op_", transicoesCombinadas);
copiarTransicoesModulo(moduloFuncoes, "func_", transicoesCombinadas);
copiarTransicoesModulo(moduloParenteses, "paren_", transicoesCombinadas);
// Conecta estados finais de módulos ao estado final unificado
for (const auto& estadoFinal : moduloNumeros.estadosFinais) {
transicoesCombinadas["num_" + estadoFinal + ",FIM"] = {"token_reconhecido"};
}
for (const auto& estadoFinal : moduloIdentificadores.estadosFinais) {
transicoesCombinadas["id_" + estadoFinal + ",FIM"] = {"token_reconhecido"};
}
for (const auto& estadoFinal : moduloOperadores.estadosFinais) {
transicoesCombinadas["op_" + estadoFinal + ",FIM"] = {"token_reconhecido"};
}
for (const auto& estadoFinal : moduloFuncoes.estadosFinais) {
transicoesCombinadas["func_" + estadoFinal + ",FIM"] = {"token_reconhecido"};
}
for (const auto& estadoFinal : moduloParenteses.estadosFinais) {
transicoesCombinadas["paren_" + estadoFinal + ",FIM"] = {"token_reconhecido"};
}
return AFN(estadosCombinados, transicoesCombinadas, "expr_inicio", estadosFinaisCombinados);
}
void copiarTransicoesModulo(const AFN& modulo, const std::string& prefixo,
std::unordered_map<std::string, std::unordered_set<std::string>>& destino) {
for (const auto& entrada : modulo.transicoes) {
const std::string& chaveOriginal = entrada.first;
const std::unordered_set<std::string>& estadosDestino = entrada.second;
std::string chaveNova = prefixo + chaveOriginal;
std::unordered_set<std::string> estadosDestinoNovos;
for (const auto& estado : estadosDestino) {
estadosDestinoNovos.insert(prefixo + estado);
}
destino[chaveNova] = estadosDestinoNovos;
}
}
struct ResultadoAnaliseToken {
std::string token;
bool aceito;
std::string tipoToken;
std::unordered_map<std::string, bool> resultadosModulos;
std::vector<std::string> rastreamento;
};
ResultadoAnaliseToken analisarToken(const std::string& token) {
/*
Demonstra como estrutura modular facilita:
- Debugging (pode testar cada módulo separadamente)
- Manutenção (mudanças em um módulo não afetam outros)
- Extensibilidade (novos tipos de token são novos módulos)
*/
std::cout << "🏗️ Analisando token '" << token << "' com arquitetura modular...\n";
// Primeiro, testa cada módulo individualmente para debug
std::unordered_map<std::string, bool> resultadosModulos;
resultadosModulos["Números"] = testarModulo(moduloNumeros, token);
resultadosModulos["Identificadores"] = testarModulo(moduloIdentificadores, token);
resultadosModulos["Operadores"] = testarModulo(moduloOperadores, token);
resultadosModulos["Funções"] = testarModulo(moduloFuncoes, token);
resultadosModulos["Parênteses"] = testarModulo(moduloParenteses, token);
// Depois testa o AFN combinado
auto tokens = tokenizarEntrada(token);
std::unordered_set<std::string> estadosAtivos = {"expr_inicio"};
std::vector<std::string> rastreamento;
for (const auto& t : tokens) {
std::unordered_set<std::string> novosEstados;
for (const auto& estado : estadosAtivos) {
std::string chave = estado + "," + t;
if (afnExpressaoCompleta.transicoes.count(chave)) {
for (const auto& destino : afnExpressaoCompleta.transicoes[chave]) {
novosEstados.insert(destino);
}
}
}
estadosAtivos = novosEstados;
rastreamento.push_back("Após '" + t + "': " + std::to_string(estadosAtivos.size()) + " estados ativos");
if (estadosAtivos.empty()) break;
}
bool aceito = std::any_of(estadosAtivos.begin(), estadosAtivos.end(),
[this](const std::string& estado) {
return afnExpressaoCompleta.estadosFinais.count(estado) > 0;
});
std::string tipoToken = determinarTipoToken(token, resultadosModulos);
return {token, aceito, tipoToken, resultadosModulos, rastreamento};
}
bool testarModulo(const AFN& modulo, const std::string& entrada) {
auto tokens = tokenizarEntrada(entrada);
std::unordered_set<std::string> estadosAtivos = {modulo.estadoInicial};
for (const auto& token : tokens) {
std::unordered_set<std::string> novosEstados;
for (const auto& estado : estadosAtivos) {
std::string chave = estado + "," + token;
if (modulo.transicoes.count(chave)) {
for (const auto& destino : modulo.transicoes.at(chave)) {
novosEstados.insert(destino);
}
}
}
estadosAtivos = novosEstados;
if (estadosAtivos.empty()) return false;
}
return std::any_of(estadosAtivos.begin(), estadosAtivos.end(),
[&modulo](const std::string& estado) {
return modulo.estadosFinais.count(estado) > 0;
});
}
std::string determinarTipoToken(const std::string& token,
const std::unordered_map<std::string, bool>& resultados) {
if (resultados.at("Números")) return "NUMERO";
if (resultados.at("Funções")) return "FUNCAO";
if (resultados.at("Identificadores")) return "IDENTIFICADOR";
if (resultados.at("Operadores")) return "OPERADOR";
if (resultados.at("Parênteses")) return "PARENTESE";
return "DESCONHECIDO";
}
std::vector<std::string> tokenizarEntrada(const std::string& entrada) {
std::vector<std::string> tokens;
for (char c : entrada) {
if (c >= '0' && c <= '9') {
tokens.push_back("DIGITO");
} else if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
tokens.push_back("LETRA");
} else {
tokens.push_back(std::string(1, c));
}
}
tokens.push_back("FIM");
return tokens;
}
void demonstrarEstruturaModular() {
std::cout << "🎯 Estratégia: Mantenha Estrutura Modular\n";
std::cout << std::string(60, '=') << "\n";
std::cout << "📚 Contexto: Analisador de Expressões Matemáticas\n\n";
std::vector<std::string> casosTest = {
"123", // Número
"3.14", // Decimal
"x", // Identificador
"sin", // Função
"+", // Operador
"**", // Operador duplo
"(", // Parêntese
"temp_var", // Identificador complexo
"2.5e10", // Científico
"cos" // Função
};
for (const auto& caso : casosTest) {
std::cout << "🧪 Analisando: '" << caso << "'\n";
auto resultado = analisarToken(caso);
std::cout << " Resultado: " << (resultado.aceito ? "✓" : "✗")
<< " " << resultado.tipoToken << "\n";
std::cout << " Módulos que aceitaram:\n";
for (const auto& entrada : resultado.resultadosModulos) {
if (entrada.second) {
std::cout << " ✓ " << entrada.first << "\n";
}
}
std::cout << " Passos de processamento: " << resultado.rastreamento.size() << "\n\n";
}
std::cout << "💡 Benefícios da Estrutura Modular:\n";
std::cout << " • Cada módulo pode ser desenvolvido independentemente\n";
std::cout << " • Debugging é isolado por módulo\n";
std::cout << " • Fácil adição de novos tipos de token\n";
std::cout << " • Manutenção localizada (mudança em um módulo)\n";
std::cout << " • Testabilidade aprimorada\n";
std::cout << " • Reutilização de módulos em outros projetos\n";
std::cout << "\n🏗️ Arquitetura Modular em Ação:\n";
std::cout << " • 5 módulos independentes especializados\n";
std::cout << " • Integração não-determinística elegante\n";
std::cout << " • Estados com prefixos evitam conflitos\n";
std::cout << " • Debug por módulo + debug integrado\n";
}
};
// Demonstração
int main() {
std::cout << "🔬 Demonstração: Estrutura Modular para Compiladores\n\n";
AnalisadorExpressoesModular analisador;
analisador.demonstrarEstruturaModular();
return 0;
}Estratégia 4: Teste Incrementalmente 🧪
Caso Real: Validação Progressiva de Gramáticas Livres de Contexto
Imagine que seu grupo está desenvolvendo um parser para uma linguagem que suporta estruturas de controle aninhadas, declarações de função, e expressões complexas. A estratégia de teste incremental permite validar cada componente isoladamente antes da integração, evitando bugs difíceis de rastrear em gramáticas complexas.
O Desafio Prático: Gramáticas livres de contexto para linguagens reais podem ter centenas de regras de produção. Testar toda a gramática de uma vez torna impossível localizar a fonte de conflitos, ambiguidades, ou comportamentos inesperados.
graph TB
subgraph "Teste Incremental de Gramáticas"
A[Expressões Simples] --> B[Testes Unitários]
B --> C[Expressões com Precedência]
C --> D[Testes de Precedência]
D --> E[Estruturas de Controle]
E --> F[Testes de Aninhamento]
F --> G[Declarações de Função]
G --> H[Testes de Escopo]
H --> I[Gramática Completa]
I --> J[Testes de Integração]
end
style B fill:#e8f5e8
style D fill:#e8f5e8
style F fill:#e8f5e8
style H fill:#e8f5e8
style J fill:#90EE90
🎯 Síntese das Estratégias Aplicadas ao Desenvolvimento de Compiladores
As quatro estratégias que exploramos através de casos reais demonstram como o design sistemático de AFNs pode transformar o desenvolvimento de compiladores de uma atividade complexa e propensa a erros em um processo estruturado e confiável.
Estratégia 1 - Comece com Casos Simples mostrou como a evolução incremental permite construir analisadores léxicos robustos começando com tokens básicos e adicionando complexidade gradualmente. Esta abordagem é fundamental para evitar a sobrecarga cognitiva e garantir que cada componente seja completamente validado antes da próxima fase.
Estratégia 2 - Use Não-Determinismo para Alternativas revelou como AFNs podem lidar elegantemente com ambiguidades inerentes ao processamento de linguagens. Múltiplas notações para literais, palavras-chave versus identificadores, e operadores com significados contextuais são resolvidos naturalmente pelo não-determinismo.
Estratégia 3 - Mantenha Estrutura Modular demonstrou como decomposição funcional permite desenvolvimento paralelo, debugging isolado, e manutenção localizada. Cada tipo de token torna-se um módulo especializado que pode ser desenvolvido, testado, e otimizado independentemente.
Estratégia 4 - Teste Incrementalmente enfatiza a importância de validação contínua durante o desenvolvimento. Cada adição à gramática ou ao analisador deve ser acompanhada de testes específicos que exercitem os novos recursos sem quebrar funcionalidades existentes.
Padrões Comuns de Construção
Certos padrões de construção aparecem repetidamente quando trabalhamos com AFNs, e reconhecê-los pode acelerar significativamente o processo de design.
Padrão de escolha inicial: Para reconhecer linguagens que são uniões de sublinguagens, use um estado inicial com transições não-determinísticas para estados que iniciam o reconhecimento de cada sublinguagem.
Padrão de busca flexível: Para reconhecer palavras que contêm determinados subpadrões em qualquer posição, use um laço no estado inicial que permite “pular” símbolos irrelevantes, combinado com transições não-determinísticas que iniciam o reconhecimento do subpadrão desejado.
Padrão de confirmação múltipla: Para padrões que podem ser interpretados de múltiplas formas até que contexto adicional resolva a ambiguidade, mantenha múltiplos caminhos de processamento ativos até que a decisão final possa ser tomada.
Exemplos Ilustrativos de Construção
Vamos explorar a construção de AFNs através de exemplos progressivamente mais sofisticados que demonstram as técnicas e padrões discutidos.
Estados e Seus Significados:
q0 (Estado Inicial) 🏁
- Representa: “Ainda não encontrei nenhum padrão relevante”
- Função: Estado de busca ativa por padrões
- Transições:
- Com ‘a’: vai para {q0, q1, q3} (não-determinismo!)
- Com ‘b’: permanece em {q0}
q1 🔍
- Representa: “Acabei de ler um ‘a’ e estou tentando formar ‘ab’”
- Função: Estado intermediário para reconhecer o padrão ‘ab’
- Transições:
- Com ‘b’: vai para q2 (sucesso! encontrei ‘ab’)
- Com ‘a’: morrem (este caminho falha)
q2 ✅
- Representa: “Já encontrei o padrão ‘ab’ - palavra aceita!”
- Função: Estado final - qualquer coisa que venha depois mantém aceitação
- Transições:
- Com ‘a’ ou ‘b’: permanece em q2 (já aceitou, qualquer continuação é válida)
q3 🎯
- Representa: “Acabei de ler um ‘a’ e estou construindo uma palavra que pode terminar em ‘ba’”
- Função: Estado que “lembra” do ‘a’ anterior para formar ‘ba’
- Transições:
- Com ‘a’: permanece em q3 (atualiza o ‘a’ lembrado)
- Com ‘b’: vai para q4 (pode estar terminando com ‘ba’)
q4 🏆
- Representa: “A palavra termina com ‘ba’ - aceita!”
- Função: Estado final para palavras terminadas em ‘ba’
- Observação: Este estado SÓ aceita se a palavra realmente terminar aqui
🌊 O Não-Determinismo em Ação: Quando o AFN lê um ‘a’ no estado q0, ele simultaneamente:
- Permanece em q0 (continua buscando padrões)
- Vai para q1 (tenta formar ‘ab’)
- Vai para q3 (tenta formar uma palavra terminando em ‘ba’)
class AFN:
def __init__(self, estados, alfabeto, transicoes, estado_inicial, estados_finais):
self.estados = estados
self.alfabeto = alfabeto
self.transicoes = transicoes # dict: (estado, simbolo) -> set de estados
self.estado_inicial = estado_inicial
self.estados_finais = estados_finais
def processar_simbolo(self, estados_ativos, simbolo):
"""Processa um símbolo e retorna novos estados ativos"""
novos_estados = set()
for estado in estados_ativos:
if (estado, simbolo) in self.transicoes:
novos_estados.update(self.transicoes[(estado, simbolo)])
return novos_estados
def aceita_palavra(self, palavra):
"""Verifica se a palavra é aceita pelo AFN"""
estados_ativos = {self.estado_inicial}
for simbolo in palavra:
estados_ativos = self.processar_simbolo(estados_ativos, simbolo)
if not estados_ativos: # Nenhum estado ativo
return False
return bool(estados_ativos.intersection(self.estados_finais))
# Exemplo: AFN que aceita palavras contendo 'ab' ou terminando com 'ba'
def criar_afn_exemplo():
estados = {'q0', 'q1', 'q2', 'q3', 'q4'}
alfabeto = {'a', 'b'}
transicoes = {
('q0', 'a'): {'q0', 'q1', 'q3'}, # Não-determinismo
('q0', 'b'): {'q0'},
('q1', 'b'): {'q2'}, # Reconhece 'ab'
('q2', 'a'): {'q2'}, # Mantém aceitação
('q2', 'b'): {'q2'},
('q3', 'a'): {'q3'},
('q3', 'b'): {'q4'}, # Termina com 'ba'
}
return AFN(estados, alfabeto, transicoes, 'q0', {'q2', 'q4'})class AFN {
constructor(estados, alfabeto, transicoes, estadoInicial, estadosFinais) {
this.estados = new Set(estados);
this.alfabeto = new Set(alfabeto);
this.transicoes = new Map(transicoes);
this.estadoInicial = estadoInicial;
this.estadosFinais = new Set(estadosFinais);
}
processarSimbolo(estadosAtivos, simbolo) {
const novosEstados = new Set();
for (const estado of estadosAtivos) {
const chave = `${estado},${simbolo}`;
if (this.transicoes.has(chave)) {
for (const novoEstado of this.transicoes.get(chave)) {
novosEstados.add(novoEstado);
}
}
}
return novosEstados;
}
aceitaPalavra(palavra) {
let estadosAtivos = new Set([this.estadoInicial]);
for (const simbolo of palavra) {
estadosAtivos = this.processarSimbolo(estadosAtivos, simbolo);
if (estadosAtivos.size === 0) {
return false;
}
}
return [...estadosAtivos].some(estado =>
this.estadosFinais.has(estado)
);
}
}
// Criação do AFN exemplo
function criarAFNExemplo() {
const transicoes = new Map([
['q0,a', ['q0', 'q1', 'q3']],
['q0,b', ['q0']],
['q1,b', ['q2']],
['q2,a', ['q2']],
['q2,b', ['q2']],
['q3,a', ['q3']],
['q3,b', ['q4']]
]);
return new AFN(
['q0', 'q1', 'q2', 'q3', 'q4'],
['a', 'b'],
transicoes,
'q0',
['q2', 'q4']
);
}import java.util.*;
public class AFN {
private Set<String> estados;
private Set<Character> alfabeto;
private Map<String, Set<String>> transicoes;
private String estadoInicial;
private Set<String> estadosFinais;
public AFN(Set<String> estados, Set<Character> alfabeto,
Map<String, Set<String>> transicoes,
String estadoInicial, Set<String> estadosFinais) {
this.estados = new HashSet<>(estados);
this.alfabeto = new HashSet<>(alfabeto);
this.transicoes = new HashMap<>(transicoes);
this.estadoInicial = estadoInicial;
this.estadosFinais = new HashSet<>(estadosFinais);
}
private Set<String> processarSimbolo(Set<String> estadosAtivos, char simbolo) {
Set<String> novosEstados = new HashSet<>();
for (String estado : estadosAtivos) {
String chave = estado + "," + simbolo;
Set<String> destinos = transicoes.get(chave);
if (destinos != null) {
novosEstados.addAll(destinos);
}
}
return novosEstados;
}
public boolean aceitaPalavra(String palavra) {
Set<String> estadosAtivos = new HashSet<>();
estadosAtivos.add(estadoInicial);
for (char simbolo : palavra.toCharArray()) {
estadosAtivos = processarSimbolo(estadosAtivos, simbolo);
if (estadosAtivos.isEmpty()) {
return false;
}
}
return estadosAtivos.stream()
.anyMatch(estadosFinais::contains);
}
public static AFN criarExemplo() {
Set<String> estados = Set.of("q0", "q1", "q2", "q3", "q4");
Set<Character> alfabeto = Set.of('a', 'b');
Map<String, Set<String>> transicoes = new HashMap<>();
transicoes.put("q0,a", Set.of("q0", "q1", "q3"));
transicoes.put("q0,b", Set.of("q0"));
transicoes.put("q1,b", Set.of("q2"));
transicoes.put("q2,a", Set.of("q2"));
transicoes.put("q2,b", Set.of("q2"));
transicoes.put("q3,a", Set.of("q3"));
transicoes.put("q3,b", Set.of("q4"));
return new AFN(estados, alfabeto, transicoes, "q0",
Set.of("q2", "q4"));
}
}using System;
using System.Collections.Generic;
using System.Linq;
public class AFN
{
private HashSet<string> estados;
private HashSet<char> alfabeto;
private Dictionary<string, HashSet<string>> transicoes;
private string estadoInicial;
private HashSet<string> estadosFinais;
public AFN(IEnumerable<string> estados, IEnumerable<char> alfabeto,
Dictionary<string, HashSet<string>> transicoes,
string estadoInicial, IEnumerable<string> estadosFinais)
{
this.estados = new HashSet<string>(estados);
this.alfabeto = new HashSet<char>(alfabeto);
this.transicoes = new Dictionary<string, HashSet<string>>(transicoes);
this.estadoInicial = estadoInicial;
this.estadosFinais = new HashSet<string>(estadosFinais);
}
private HashSet<string> ProcessarSimbolo(HashSet<string> estadosAtivos, char simbolo)
{
var novosEstados = new HashSet<string>();
foreach (var estado in estadosAtivos)
{
var chave = $"{estado},{simbolo}";
if (transicoes.ContainsKey(chave))
{
novosEstados.UnionWith(transicoes[chave]);
}
}
return novosEstados;
}
public bool AceitaPalavra(string palavra)
{
var estadosAtivos = new HashSet<string> { estadoInicial };
foreach (char simbolo in palavra)
{
estadosAtivos = ProcessarSimbolo(estadosAtivos, simbolo);
if (!estadosAtivos.Any())
return false;
}
return estadosAtivos.Intersect(estadosFinais).Any();
}
public static AFN CriarExemplo()
{
var transicoes = new Dictionary<string, HashSet<string>>
{
{"q0,a", new HashSet<string> {"q0", "q1", "q3"}},
{"q0,b", new HashSet<string> {"q0"}},
{"q1,b", new HashSet<string> {"q2"}},
{"q2,a", new HashSet<string> {"q2"}},
{"q2,b", new HashSet<string> {"q2"}},
{"q3,a", new HashSet<string> {"q3"}},
{"q3,b", new HashSet<string> {"q4"}}
};
return new AFN(
new[] {"q0", "q1", "q2", "q3", "q4"},
new[] {'a', 'b'},
transicoes,
"q0",
new[] {"q2", "q4"}
);
}
}package main
import (
"fmt"
)
type AFN struct {
estados map[string]bool
alfabeto map[rune]bool
transicoes map[string]map[string]bool
estadoInicial string
estadosFinais map[string]bool
}
func NewAFN(estados []string, alfabeto []rune,
transicoes map[string][]string,
estadoInicial string, estadosFinais []string) *AFN {
afn := &AFN{
estados: make(map[string]bool),
alfabeto: make(map[rune]bool),
transicoes: make(map[string]map[string]bool),
estadoInicial: estadoInicial,
estadosFinais: make(map[string]bool),
}
for _, estado := range estados {
afn.estados[estado] = true
}
for _, simbolo := range alfabeto {
afn.alfabeto[simbolo] = true
}
for chave, destinos := range transicoes {
afn.transicoes[chave] = make(map[string]bool)
for _, destino := range destinos {
afn.transicoes[chave][destino] = true
}
}
for _, estado := range estadosFinais {
afn.estadosFinais[estado] = true
}
return afn
}
func (afn *AFN) processarSimbolo(estadosAtivos map[string]bool, simbolo rune) map[string]bool {
novosEstados := make(map[string]bool)
for estado := range estadosAtivos {
chave := fmt.Sprintf("%s,%c", estado, simbolo)
if destinos, existe := afn.transicoes[chave]; existe {
for destino := range destinos {
novosEstados[destino] = true
}
}
}
return novosEstados
}
func (afn *AFN) AceitaPalavra(palavra string) bool {
estadosAtivos := map[string]bool{afn.estadoInicial: true}
for _, simbolo := range palavra {
estadosAtivos = afn.processarSimbolo(estadosAtivos, simbolo)
if len(estadosAtivos) == 0 {
return false
}
}
for estado := range estadosAtivos {
if afn.estadosFinais[estado] {
return true
}
}
return false
}
func CriarAFNExemplo() *AFN {
transicoes := map[string][]string{
"q0,a": {"q0", "q1", "q3"},
"q0,b": {"q0"},
"q1,b": {"q2"},
"q2,a": {"q2"},
"q2,b": {"q2"},
"q3,a": {"q3"},
"q3,b": {"q4"},
}
return NewAFN(
[]string{"q0", "q1", "q2", "q3", "q4"},
[]rune{'a', 'b'},
transicoes,
"q0",
[]string{"q2", "q4"},
)
}class AFN {
final Set<String> estados;
final Set<String> alfabeto;
final Map<String, Set<String>> transicoes;
final String estadoInicial;
final Set<String> estadosFinais;
AFN({
required this.estados,
required this.alfabeto,
required this.transicoes,
required this.estadoInicial,
required this.estadosFinais,
});
Set<String> _processarSimbolo(Set<String> estadosAtivos, String simbolo) {
final novosEstados = <String>{};
for (final estado in estadosAtivos) {
final chave = '$estado,$simbolo';
final destinos = transicoes[chave];
if (destinos != null) {
novosEstados.addAll(destinos);
}
}
return novosEstados;
}
bool aceitaPalavra(String palavra) {
var estadosAtivos = <String>{estadoInicial};
for (int i = 0; i < palavra.length; i++) {
final simbolo = palavra[i];
estadosAtivos = _processarSimbolo(estadosAtivos, simbolo);
if (estadosAtivos.isEmpty) {
return false;
}
}
return estadosAtivos.any((estado) => estadosFinais.contains(estado));
}
static AFN criarExemplo() {
final transicoes = <String, Set<String>>{
'q0,a': {'q0', 'q1', 'q3'},
'q0,b': {'q0'},
'q1,b': {'q2'},
'q2,a': {'q2'},
'q2,b': {'q2'},
'q3,a': {'q3'},
'q3,b': {'q4'},
};
return AFN(
estados: {'q0', 'q1', 'q2', 'q3', 'q4'},
alfabeto: {'a', 'b'},
transicoes: transicoes,
estadoInicial: 'q0',
estadosFinais: {'q2', 'q4'},
);
}
}#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <vector>
class AFN {
private:
std::unordered_set<std::string> estados;
std::unordered_set<char> alfabeto;
std::unordered_map<std::string, std::unordered_set<std::string>> transicoes;
std::string estadoInicial;
std::unordered_set<std::string> estadosFinais;
public:
AFN(const std::vector<std::string>& est,
const std::vector<char>& alf,
const std::unordered_map<std::string, std::vector<std::string>>& trans,
const std::string& inicial,
const std::vector<std::string>& finais)
: estadoInicial(inicial) {
for (const auto& e : est) estados.insert(e);
for (char c : alf) alfabeto.insert(c);
for (const auto& f : finais) estadosFinais.insert(f);
for (const auto& [chave, destinos] : trans) {
for (const auto& destino : destinos) {
transicoes[chave].insert(destino);
}
}
}
std::unordered_set<std::string> processarSimbolo(
const std::unordered_set<std::string>& estadosAtivos,
char simbolo) {
std::unordered_set<std::string> novosEstados;
for (const auto& estado : estadosAtivos) {
std::string chave = estado + "," + simbolo;
auto it = transicoes.find(chave);
if (it != transicoes.end()) {
for (const auto& destino : it->second) {
novosEstados.insert(destino);
}
}
}
return novosEstados;
}
bool aceitaPalavra(const std::string& palavra) {
std::unordered_set<std::string> estadosAtivos = {estadoInicial};
for (char simbolo : palavra) {
estadosAtivos = processarSimbolo(estadosAtivos, simbolo);
if (estadosAtivos.empty()) {
return false;
}
}
for (const auto& estado : estadosAtivos) {
if (estadosFinais.count(estado)) {
return true;
}
}
return false;
}
static AFN criarExemplo() {
std::unordered_map<std::string, std::vector<std::string>> transicoes = {
{"q0,a", {"q0", "q1", "q3"}},
{"q0,b", {"q0"}},
{"q1,b", {"q2"}},
{"q2,a", {"q2"}},
{"q2,b", {"q2"}},
{"q3,a", {"q3"}},
{"q3,b", {"q4"}}
};
return AFN(
{"q0", "q1", "q2", "q3", "q4"},
{'a', 'b'},
transicoes,
"q0",
{"q2", "q4"}
);
}
};use std::collections::{HashMap, HashSet};
#[derive(Debug, Clone)]
pub struct AFN {
estados: HashSet<String>,
alfabeto: HashSet<char>,
transicoes: HashMap<String, HashSet<String>>,
estado_inicial: String,
estados_finais: HashSet<String>,
}
impl AFN {
pub fn new(
estados: Vec<String>,
alfabeto: Vec<char>,
transicoes: HashMap<String, Vec<String>>,
estado_inicial: String,
estados_finais: Vec<String>,
) -> Self {
let mut trans_map = HashMap::new();
for (chave, destinos) in transicoes {
trans_map.insert(chave, destinos.into_iter().collect());
}
AFN {
estados: estados.into_iter().collect(),
alfabeto: alfabeto.into_iter().collect(),
transicoes: trans_map,
estado_inicial,
estados_finais: estados_finais.into_iter().collect(),
}
}
fn processar_simbolo(&self, estados_ativos: &HashSet<String>, simbolo: char) -> HashSet<String> {
let mut novos_estados = HashSet::new();
for estado in estados_ativos {
let chave = format!("{},{}", estado, simbolo);
if let Some(destinos) = self.transicoes.get(&chave) {
novos_estados.extend(destinos.iter().cloned());
}
}
novos_estados
}
pub fn aceita_palavra(&self, palavra: &str) -> bool {
let mut estados_ativos = std::iter::once(self.estado_inicial.clone()).collect();
for simbolo in palavra.chars() {
estados_ativos = self.processar_simbolo(&estados_ativos, simbolo);
if estados_ativos.is_empty() {
return false;
}
}
estados_ativos.intersection(&self.estados_finais).next().is_some()
}
pub fn criar_exemplo() -> Self {
let mut transicoes = HashMap::new();
transicoes.insert("q0,a".to_string(), vec!["q0".to_string(), "q1".to_string(), "q3".to_string()]);
transicoes.insert("q0,b".to_string(), vec!["q0".to_string()]);
transicoes.insert("q1,b".to_string(), vec!["q2".to_string()]);
transicoes.insert("q2,a".to_string(), vec!["q2".to_string()]);
transicoes.insert("q2,b".to_string(), vec!["q2".to_string()]);
transicoes.insert("q3,a".to_string(), vec!["q3".to_string()]);
transicoes.insert("q3,b".to_string(), vec!["q4".to_string()]);
AFN::new(
vec!["q0".to_string(), "q1".to_string(), "q2".to_string(),
"q3".to_string(), "q4".to_string()],
vec!['a', 'b'],
transicoes,
"q0".to_string(),
vec!["q2".to_string(), "q4".to_string()],
)
}
}module AFN = struct
type t = {
estados : string list;
alfabeto : char list;
transicoes : (string * char, string list) Hashtbl.t;
estado_inicial : string;
estados_finais : string list;
}
let criar estados alfabeto transicoes estado_inicial estados_finais =
let tbl = Hashtbl.create 16 in
List.iter (fun ((estado, simbolo), destinos) ->
Hashtbl.add tbl (estado, simbolo) destinos
) transicoes;
{
estados;
alfabeto;
transicoes = tbl;
estado_inicial;
estados_finais;
}
let processar_simbolo afn estados_ativos simbolo =
List.fold_left (fun acc estado ->
match Hashtbl.find_opt afn.transicoes (estado, simbolo) with
| Some destinos -> destinos @ acc
| None -> acc
) [] estados_ativos
|> List.sort_uniq String.compare
let aceita_palavra afn palavra =
let chars = List.of_seq (String.to_seq palavra) in
let rec loop estados_ativos = function
| [] ->
List.exists (fun estado ->
List.mem estado afn.estados_finais
) estados_ativos
| simbolo :: resto ->
let novos_estados = processar_simbolo afn estados_ativos simbolo in
if novos_estados = [] then false
else loop novos_estados resto
in
loop [afn.estado_inicial] chars
let criar_exemplo () =
let transicoes = [
(("q0", 'a'), ["q0"; "q1"; "q3"]);
(("q0", 'b'), ["q0"]);
(("q1", 'b'), ["q2"]);
(("q2", 'a'), ["q2"]);
(("q2", 'b'), ["q2"]);
(("q3", 'a'), ["q3"]);
(("q3", 'b'), ["q4"]);
] in
criar
["q0"; "q1"; "q2"; "q3"; "q4"]
['a'; 'b']
transicoes
"q0"
["q2"; "q4"]
endimport qualified Data.Set as Set
import qualified Data.Map as Map
import Data.List (foldl')
data AFN = AFN
{ estados :: Set.Set String
, alfabeto :: Set.Set Char
, transicoes :: Map.Map (String, Char) (Set.Set String)
, estadoInicial :: String
, estadosFinais :: Set.Set String
} deriving (Show, Eq)
criarAFN :: [String] -> [Char] -> [((String, Char), [String])] -> String -> [String] -> AFN
criarAFN ests alf trans inicial finais = AFN
{ estados = Set.fromList ests
, alfabeto = Set.fromList alf
, transicoes = Map.fromList [(k, Set.fromList v) | (k, v) <- trans]
, estadoInicial = inicial
, estadosFinais = Set.fromList finais
}
processarSimbolo :: AFN -> Set.Set String -> Char -> Set.Set String
processarSimbolo afn estadosAtivos simbolo =
Set.fold (\estado acc ->
case Map.lookup (estado, simbolo) (transicoes afn) of
Just destinos -> Set.union acc destinos
Nothing -> acc
) Set.empty estadosAtivos
aceitaPalavra :: AFN -> String -> Bool
aceitaPalavra afn palavra =
let estadosIniciais = Set.singleton (estadoInicial afn)
estadosFinaisComputacao = foldl' (processarSimbolo afn) estadosIniciais palavra
in not (Set.null (Set.intersection estadosFinaisComputacao (estadosFinais afn)))
criarExemplo :: AFN
criarExemplo = criarAFN
["q0", "q1", "q2", "q3", "q4"]
['a', 'b']
[ (("q0", 'a'), ["q0", "q1", "q3"])
, (("q0", 'b'), ["q0"])
, (("q1", 'b'), ["q2"])
, (("q2", 'a'), ["q2"])
, (("q2", 'b'), ["q2"])
, (("q3", 'a'), ["q3"])
, (("q3", 'b'), ["q4"])
]
"q0"
["q2", "q4"]Este exemplo ilustra um AFN que reconhece palavras que contêm o subpadrão ‘ab’ em qualquer posição ou que terminam com ‘ba’. O não-determinismo é evidente na transição \delta(q_0, a) = \{q_0, q_1, q_3\}, que permite ao autômato simultaneamente continuar procurando por padrões (permanecendo em q_0), iniciar o reconhecimento de ‘ab’ (indo para q_1), e iniciar o reconhecimento de uma palavra terminando em ‘ba’ (indo para q_3).
Visualizando o Comportamento Não-Determinístico
Para realmente compreender como AFNs processam informação, é fundamental visualizar o comportamento do conjunto de estados ativos durante o processamento de palavras específicas.
graph TD
subgraph "Processamento da palavra 'aab'"
A["Início: {q0}"] --> B["Após 'a': {q0, q1, q3}"]
B --> C["Após 'aa': {q0, q1, q3}"]
C --> D["Após 'aab': {q0, q2, q4}"]
end
subgraph "Estados de aceitação"
E[q2: aceita 'ab']
F[q4: aceita terminação em 'ba']
end
D --> E
D --> F
style D fill:#90EE90
style E fill:#FFD700
style F fill:#FFD700
Esta visualização revela como o não-determinismo permite que o autômato “aposte” em múltiplas interpretações simultaneamente. Quando processa ‘a’, ele mantém a possibilidade de que este seja o início de ‘ab’, o início de uma sequência que terminará em ‘ba’, ou simplesmente um caractere a ser ignorado na busca por padrões futuros.
A força do não-determinismo fica evidente quando comparamos este AFN com um AFD equivalente. O AFD correspondente precisaria de estados que codificam explicitamente todas as combinações possíveis de “memória” sobre prefixos parcialmente reconhecidos, resultando em uma máquina significativamente mais complexa.
A elegância conceitual do AFN permite focar na lógica essencial do reconhecimento sem se distrair com os detalhes de como gerenciar eficientemente múltiplas possibilidades simultaneamente. Esta separação de preocupações é uma das principais virtudes do não-determinismo como ferramenta de design.
🔄 A Arte da Conversão: De AFN para AFD
Uma das descobertas mais surpreendentes da teoria da computação é que todo autômato finito não-determinístico pode ser convertido em um autômato finito determinístico equivalente. Esta equivalência não é apenas um resultado teórico interessante - é a base para implementações práticas que combinam a elegância conceitual dos AFNs com a eficiência computacional dos AFDs.
O algoritmo de conversão, conhecido como construção de subconjuntos ou algoritmo de determinização, oferece um processo sistemático para eliminar o não-determinismo mantendo exatamente a mesma capacidade de reconhecimento. Compreender este algoritmo é fundamental para qualquer pessoa que trabalhe com processamento de linguagens formais.
🛠️ Algoritmo de Construção de Subconjuntos
Ideia Central: Cada estado do AFD resultante corresponde a um subconjunto de estados do AFN original. Este estado representa todas as possibilidades de processamento que o AFN poderia estar explorando simultaneamente.
Processo de Construção:
Estado inicial do AFD: \{q_0\} (onde q_0 é o estado inicial do AFN)
Estados do AFD: Cada subconjunto não-vazio de estados do AFN torna-se um estado potencial do AFD
Transições do AFD: Para um estado S do AFD e símbolo a: \delta_{AFD}(S, a) = \bigcup_{q \in S} \delta_{AFN}(q, a)
Estados finais do AFD: Um estado S é final se S \cap F \neq \emptyset (onde F são os estados finais do AFN)
Algoritmo incremental: Construa apenas os estados alcançáveis a partir do estado inicial
Implementação Detalhada da Conversão
A implementação prática do algoritmo de conversão requer cuidado especial com estruturas de dados e eficiência, especialmente considerando que o número de estados no AFD pode crescer exponencialmente com o número de estados no AFN.
def afn_para_afd(afn):
"""Converte AFN para AFD usando construção de subconjuntos"""
from collections import deque
# Estado inicial do AFD é conjunto contendo apenas estado inicial do AFN
estado_inicial_afd = frozenset([afn.estado_inicial])
# Estruturas para construir o AFD
estados_afd = set()
transicoes_afd = {}
estados_finais_afd = set()
# Fila para BFS da construção
fila = deque([estado_inicial_afd])
visitados = {estado_inicial_afd}
while fila:
estado_atual = fila.popleft()
estados_afd.add(estado_atual)
# Verifica se é estado final
if any(estado in afn.estados_finais for estado in estado_atual):
estados_finais_afd.add(estado_atual)
# Para cada símbolo do alfabeto
for simbolo in afn.alfabeto:
# Calcula próximo estado (união de transições)
proximo_estado = set()
for estado in estado_atual:
if (estado, simbolo) in afn.transicoes:
proximo_estado.update(afn.transicoes[(estado, simbolo)])
if proximo_estado: # Se não é vazio
proximo_estado_frozen = frozenset(proximo_estado)
# Adiciona transição
transicoes_afd[(estado_atual, simbolo)] = proximo_estado_frozen
# Se novo estado, adiciona à fila
if proximo_estado_frozen not in visitados:
fila.append(proximo_estado_frozen)
visitados.add(proximo_estado_frozen)
# Cria o AFD resultante
return AFD(
estados=estados_afd,
alfabeto=afn.alfabeto,
transicoes=transicoes_afd,
estado_inicial=estado_inicial_afd,
estados_finais=estados_finais_afd
)
def demonstrar_conversao():
"""Demonstra conversão com exemplo prático"""
# AFN que aceita palavras contendo 'ab' ou terminando com 'ba'
afn = criar_afn_exemplo()
print("AFN Original:")
print(f"Estados: {afn.estados}")
print(f"Transições: {afn.transicoes}")
# Converte para AFD
afd = afn_para_afd(afn)
print("\nAFD Resultante:")
print(f"Número de estados: {len(afd.estados)}")
# Testa algumas palavras
palavras_teste = ['ab', 'ba', 'aab', 'abba', 'aa', 'bb']
for palavra in palavras_teste:
resultado_afn = afn.aceita_palavra(palavra)
resultado_afd = afd.aceita_palavra(palavra)
print(f"'{palavra}': AFN={resultado_afn}, AFD={resultado_afd}, "
f"Equivalentes={resultado_afn == resultado_afd}")function afnParaAfd(afn) {
const estadosAfd = new Set();
const transicoesAfd = new Map();
const estadosFinaisAfd = new Set();
// Estado inicial do AFD
const estadoInicialAfd = new Set([afn.estadoInicial]);
const estadoInicialStr = Array.from(estadoInicialAfd).sort().join(',');
// BFS para construir estados alcançáveis
const fila = [estadoInicialAfd];
const visitados = new Set([estadoInicialStr]);
while (fila.length > 0) {
const estadoAtual = fila.shift();
const estadoAtualStr = Array.from(estadoAtual).sort().join(',');
estadosAfd.add(estadoAtualStr);
// Verifica se é estado final
if ([...estadoAtual].some(estado => afn.estadosFinais.has(estado))) {
estadosFinaisAfd.add(estadoAtualStr);
}
// Para cada símbolo
for (const simbolo of afn.alfabeto) {
const proximoEstado = new Set();
// Calcula união das transições
for (const estado of estadoAtual) {
const chave = `${estado},${simbolo}`;
if (afn.transicoes.has(chave)) {
for (const destino of afn.transicoes.get(chave)) {
proximoEstado.add(destino);
}
}
}
if (proximoEstado.size > 0) {
const proximoEstadoStr = Array.from(proximoEstado).sort().join(',');
// Adiciona transição
const chaveTransicao = `${estadoAtualStr},${simbolo}`;
transicoesAfd.set(chaveTransicao, proximoEstadoStr);
// Se novo, adiciona à fila
if (!visitados.has(proximoEstadoStr)) {
fila.push(proximoEstado);
visitados.add(proximoEstadoStr);
}
}
}
}
return new AFD(estadosAfd, afn.alfabeto, transicoesAfd,
estadoInicialStr, estadosFinaisAfd);
}import java.util.*;
import java.util.stream.Collectors;
public class ConversorAFN {
public static AFD converterParaAFD(AFN afn) {
Set<Set<String>> estadosAFD = new HashSet<>();
Map<String, String> transicoesAFD = new HashMap<>();
Set<String> estadosFinaisAFD = new HashSet<>();
// Estado inicial do AFD
Set<String> estadoInicialAFD = Set.of(afn.getEstadoInicial());
String estadoInicialStr = setParaString(estadoInicialAFD);
// BFS para construção
Queue<Set<String>> fila = new LinkedList<>();
Set<String> visitados = new HashSet<>();
fila.offer(estadoInicialAFD);
visitados.add(estadoInicialStr);
while (!fila.isEmpty()) {
Set<String> estadoAtual = fila.poll();
String estadoAtualStr = setParaString(estadoAtual);
estadosAFD.add(estadoAtual);
// Verifica se é final
if (estadoAtual.stream().anyMatch(afn.getEstadosFinais()::contains)) {
estadosFinaisAFD.add(estadoAtualStr);
}
// Para cada símbolo
for (char simbolo : afn.getAlfabeto()) {
Set<String> proximoEstado = new HashSet<>();
// União das transições
for (String estado : estadoAtual) {
String chave = estado + "," + simbolo;
Set<String> destinos = afn.getTransicoes().get(chave);
if (destinos != null) {
proximoEstado.addAll(destinos);
}
}
if (!proximoEstado.isEmpty()) {
String proximoEstadoStr = setParaString(proximoEstado);
// Adiciona transição
String chaveTransicao = estadoAtualStr + "," + simbolo;
transicoesAFD.put(chaveTransicao, proximoEstadoStr);
// Se novo, adiciona à fila
if (!visitados.contains(proximoEstadoStr)) {
fila.offer(proximoEstado);
visitados.add(proximoEstadoStr);
}
}
}
}
// Converte para formato AFD
Set<String> estadosAFDStr = estadosAFD.stream()
.map(ConversorAFN::setParaString)
.collect(Collectors.toSet());
return new AFD(estadosAFDStr, afn.getAlfabeto(),
transicoesAFD, estadoInicialStr, estadosFinaisAFD);
}
private static String setParaString(Set<String> conjunto) {
return conjunto.stream()
.sorted()
.collect(Collectors.joining(","));
}
public static void demonstrarConversao() {
AFN afn = AFN.criarExemplo();
System.out.println("AFN Original: " + afn.getEstados().size() + " estados");
AFD afd = converterParaAFD(afn);
System.out.println("AFD Resultante: " + afd.getEstados().size() + " estados");
// Testa equivalência
String[] palavrasTeste = {"ab", "ba", "aab", "abba", "aa", "bb"};
for (String palavra : palavrasTeste) {
boolean resultadoAFN = afn.aceitaPalavra(palavra);
boolean resultadoAFD = afd.aceitaPalavra(palavra);
System.out.printf("'%s': AFN=%b, AFD=%b, Equivalentes=%b%n",
palavra, resultadoAFN, resultadoAFD, resultadoAFN == resultadoAFD);
}
}
}Análise da Complexidade e Otimizações
O algoritmo de construção de subconjuntos tem complexidade temporal no pior caso de O(2^n \cdot |\Sigma| \cdot n), onde n é o número de estados do AFN e |\Sigma| é o tamanho do alfabeto. Esta complexidade exponencial é inevitável no caso geral, mas várias otimizações práticas podem melhorar significativamente a performance em casos reais.
Construção lazy (preguiçosa): Em vez de construir todos os estados possíveis, construa apenas aqueles alcançáveis a partir do estado inicial. Esta abordagem frequentemente resulta em AFDs muito menores que o limite teórico superior.
Minimização integrada: Combine o algoritmo de construção com técnicas de minimização para eliminar estados equivalentes durante a construção, reduzindo o tamanho do AFD resultante.
Detecção de padrões especiais: Para certas classes de AFNs (como aqueles derivados de expressões regulares simples), algoritmos especializados podem produzir AFDs menores mais eficientemente.
graph TB
subgraph "AFN Original"
A[q0] -->|a| B[q0,q1,q3]
A -->|b| C[q0]
D[q1] -->|b| E[q2]
F[q3] -->|a| G[q3]
F -->|b| H[q4]
end
subgraph "AFD Equivalente"
I["{q0}"] -->|a| J["{q0,q1,q3}"]
I -->|b| K["{q0}"]
J -->|a| L["{q0,q1,q3}"]
J -->|b| M["{q0,q2,q4}"]
K -->|a| J
K -->|b| K
L -->|a| L
L -->|b| M
M -->|a| N["{q0,q1,q2,q3}"]
M -->|b| O["{q0,q2}"]
end
style E fill:#90EE90
style H fill:#90EE90
style M fill:#90EE90
style N fill:#90EE90
style O fill:#90EE90
Esta visualização mostra como estados do AFN se agrupam em estados do AFD, revelando a estrutura subjacente da conversão. Estados finais no AFD são aqueles que contêm pelo menos um estado final do AFN original.
🌟 Extensões e Variações dos AFNs
O estudo dos autômatos finitos não-determinísticos naturalmente nos leva a explorar extensões e variações que ampliam ainda mais suas capacidades conceituais. Estas extensões não apenas enriquecem nossa compreensão teórica, mas também oferecem ferramentas práticas importantes para modelagem de sistemas complexos.
Autômatos com Epsilon-Transições
Uma das extensões mais naturais dos AFNs básicos são os autômatos que permitem transições vazias ou epsilon-transições. Estas são transições que podem ser executadas sem consumir nenhum símbolo da entrada, oferecendo ainda mais flexibilidade na modelagem de padrões complexos.
⚡ AFNs com Epsilon-Transições
Um AFN com epsilon-transições (AFN-ε) estende a definição básica incluindo a possibilidade de transições que não consomem entrada:
\delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathcal{P}(Q)
Onde \epsilon representa a palavra vazia. Estas transições permitem que o autômato mude de estado “gratuitamente”, sem ler nenhum símbolo da entrada.
Epsilon-fechamento: Para processar AFN-ε corretamente, definimos o epsilon-fechamento de um estado q como o conjunto de todos os estados alcançáveis a partir de q usando apenas epsilon-transições:
\text{EpsilonFecho}(q) = \{p \in Q : q \xrightarrow{\epsilon^*} p\}
A utilidade prática das epsilon-transições fica evidente ao construir autômatos para expressões regulares complexas. Elas permitem conectar subautômatos de forma elegante, especialmente ao lidar com operadores como união e concatenação.
O algoritmo de processamento para AFN-ε requer modificação para considerar o epsilon-fechamento em cada passo:
- Inicialização: Comece com o epsilon-fechamento do estado inicial
- Processamento: Para cada símbolo, aplique transições normais e depois calcule o epsilon-fechamento do resultado
- Aceitação: Aceite se algum estado final está no epsilon-fechamento final
Construção de Thompson para Expressões Regulares
Um dos algoritmos mais elegantes para construção de AFNs é o algoritmo de Thompson, que converte expressões regulares diretamente em AFN-ε usando uma abordagem compositional. Este algoritmo demonstra beautifully como conceitos teóricos podem ser transformados em algoritmos práticos eficientes.
graph TB
subgraph "Construção de Thompson"
A["Símbolo 'a'"] --> B[Estado Inicial → 'a' → Estado Final]
C["Concatenação AB"] --> D[AFN(A) → ε → AFN(B)]
E["União A|B"] --> F[Estado Inicial → ε → AFN(A)<br/>Estado Inicial → ε → AFN(B)]
G["Fechamento A*"] --> H[ε-laços para repetição]
end
style B fill:#e3f2fd
style D fill:#e8f5e8
style F fill:#fff3e0
style H fill:#f3e5f5
A construção básica segue padrões recursivos simples:
- Símbolo individual: Dois estados conectados pela transição correspondente
- Concatenação: Liga a saída do primeiro AFN à entrada do segundo usando epsilon-transições
- União: Cria novo estado inicial com epsilon-transições para ambas as alternativas
- Fechamento de Kleene: Adiciona epsilon-transições para permitir repetição
class EstadoAFN:
contador_estados = 0
def __init__(self):
self.id = EstadoAFN.contador_estados
EstadoAFN.contador_estados += 1
self.transicoes = {} # simbolo -> lista de estados
self.epsilon_transicoes = [] # lista de estados para epsilon
self.eh_final = False
class AFNThompson:
def __init__(self, inicio, fim):
self.inicio = inicio
self.fim = fim
self.fim.eh_final = True
@staticmethod
def simbolo(char):
"""Constrói AFN para símbolo único"""
inicio = EstadoAFN()
fim = EstadoAFN()
if char not in inicio.transicoes:
inicio.transicoes[char] = []
inicio.transicoes[char].append(fim)
return AFNThompson(inicio, fim)
@staticmethod
def concatenacao(afn1, afn2):
"""Constrói AFN para concatenação"""
# Liga fim do primeiro ao início do segundo
afn1.fim.epsilon_transicoes.append(afn2.inicio)
afn1.fim.eh_final = False
return AFNThompson(afn1.inicio, afn2.fim)
@staticmethod
def uniao(afn1, afn2):
"""Constrói AFN para união"""
novo_inicio = EstadoAFN()
novo_fim = EstadoAFN()
# Epsilon-transições do novo início
novo_inicio.epsilon_transicoes.extend([afn1.inicio, afn2.inicio])
# Epsilon-transições para novo fim
afn1.fim.epsilon_transicoes.append(novo_fim)
afn2.fim.epsilon_transicoes.append(novo_fim)
afn1.fim.eh_final = False
afn2.fim.eh_final = False
return AFNThompson(novo_inicio, novo_fim)
@staticmethod
def fechamento_kleene(afn):
"""Constrói AFN para fechamento de Kleene"""
novo_inicio = EstadoAFN()
novo_fim = EstadoAFN()
# Epsilon-transições para permitir zero ocorrências
novo_inicio.epsilon_transicoes.append(novo_fim)
# Epsilon-transição para o AFN original
novo_inicio.epsilon_transicoes.append(afn.inicio)
# Epsilon-transições do fim do AFN original
afn.fim.epsilon_transicoes.extend([novo_fim, afn.inicio])
afn.fim.eh_final = False
return AFNThompson(novo_inicio, novo_fim)
def epsilon_fechamento(estado, visitados=None):
"""Calcula epsilon-fechamento de um estado"""
if visitados is None:
visitados = set()
if estado.id in visitados:
return set()
visitados.add(estado.id)
fechamento = {estado}
for destino in estado.epsilon_transicoes:
fechamento.update(epsilon_fechamento(destino, visitados))
return fechamento
def construir_de_regex(regex):
"""Demonstração de construção para regex simples"""
# Exemplo simplificado: apenas concatenação e união
if len(regex) == 1:
return AFNThompson.simbolo(regex)
elif '|' in regex:
partes = regex.split('|')
afn_esq = construir_de_regex(partes[0])
afn_dir = construir_de_regex(partes[1])
return AFNThompson.uniao(afn_esq, afn_dir)
else:
# Concatenação simples
primeiro = AFNThompson.simbolo(regex[0])
for char in regex[1:]:
proximo = AFNThompson.simbolo(char)
primeiro = AFNThompson.concatenacao(primeiro, proximo)
return primeiroclass EstadoAFN {
static contadorEstados = 0;
constructor() {
this.id = EstadoAFN.contadorEstados++;
this.transicoes = new Map(); // simbolo -> array de estados
this.epsilonTransicoes = []; // array de estados
this.ehFinal = false;
}
}
class AFNThompson {
constructor(inicio, fim) {
this.inicio = inicio;
this.fim = fim;
this.fim.ehFinal = true;
}
static simbolo(char) {
const inicio = new EstadoAFN();
const fim = new EstadoAFN();
if (!inicio.transicoes.has(char)) {
inicio.transicoes.set(char, []);
}
inicio.transicoes.get(char).push(fim);
return new AFNThompson(inicio, fim);
}
static concatenacao(afn1, afn2) {
afn1.fim.epsilonTransicoes.push(afn2.inicio);
afn1.fim.ehFinal = false;
return new AFNThompson(afn1.inicio, afn2.fim);
}
static uniao(afn1, afn2) {
const novoInicio = new EstadoAFN();
const novoFim = new EstadoAFN();
novoInicio.epsilonTransicoes.push(afn1.inicio, afn2.inicio);
afn1.fim.epsilonTransicoes.push(novoFim);
afn2.fim.epsilonTransicoes.push(novoFim);
afn1.fim.ehFinal = false;
afn2.fim.ehFinal = false;
return new AFNThompson(novoInicio, novoFim);
}
static fechamentoKleene(afn) {
const novoInicio = new EstadoAFN();
const novoFim = new EstadoAFN();
novoInicio.epsilonTransicoes.push(novoFim);
novoInicio.epsilonTransicoes.push(afn.inicio);
afn.fim.epsilonTransicoes.push(novoFim, afn.inicio);
afn.fim.ehFinal = false;
return new AFNThompson(novoInicio, novoFim);
}
}
function epsilonFechamento(estado, visitados = new Set()) {
if (visitados.has(estado.id)) {
return new Set();
}
visitados.add(estado.id);
const fechamento = new Set([estado]);
for (const destino of estado.epsilonTransicoes) {
const subFechamento = epsilonFechamento(destino, new Set(visitados));
for (const est of subFechamento) {
fechamento.add(est);
}
}
return fechamento;
}Equivalência e Poder Computacional
Um dos resultados mais fundamentais da teoria de autômatos é que todas as variações que estudamos - AFDs, AFNs, e AFN-ε - são computacionalmente equivalentes. Este resultado tem implicações profundas tanto teóricas quanto práticas.
🎯 Teorema de Equivalência
Teorema: As seguintes classes de autômatos reconhecem exatamente a mesma família de linguagens (linguagens regulares):
- Autômatos Finitos Determinísticos (AFDs)
- Autômatos Finitos Não-Determinísticos (AFNs)
- Autômatos Finitos com Epsilon-Transições (AFN-ε)
- Expressões Regulares
Implicações práticas: Você pode escolher a ferramenta mais adequada para cada situação sem perder poder expressivo. Use AFNs para design elegante, AFDs para implementação eficiente, e epsilon-transições para construção modular.
A prova desta equivalência é construtiva, fornecendo algoritmos explícitos para conversão entre todas as representações. Esta característica construtiva é fundamental para implementações práticas de compiladores e processadores de texto.
As implicações de design são transformadoras: você pode projetar usando a representação mais natural para o problema, sabendo que sempre pode converter para a representação mais eficiente para implementação.
A perspectiva de complexidade revela que, embora as representações sejam equivalentes em poder expressivo, elas diferem drasticamente em eficiência de espaço e tempo. AFDs oferecem reconhecimento linear, AFNs requerem simulação potencialmente exponencial, mas epsilon-transições simplificam construção.
🔗 Integração de Múltiplos AFDs em um AFN Unificado
🎯 Reflexões sobre a Consolidação do Analisador Léxico
Esta semana representa um marco transformador no desenvolvimento do compilador Didágica. Após implementar AFDs individuais para cada categoria de token nas semanas anteriores, agora enfrento o desafio fascinante de integrá-los em um sistema unificado e robusto. A escolha estratégica de utilizar um AFN como etapa intermediária revela-se pedagogicamente brilhante, pois demonstra concretamente como o não-determinismo simplifica o design modular antes da conversão final para um AFD otimizado.
A beleza desta abordagem reside na clareza conceitual: cada AFD individual que construí representa um “especialista” que reconhece uma categoria específica de tokens. O AFN unificado age como um “orquestrador” que permite que todos esses especialistas trabalhem simultaneamente, explorando múltiplas possibilidades em paralelo. Finalmente, a conversão para AFD elimina o não-determinismo, produzindo um analisador determinístico e eficiente que preserva toda a funcionalidade dos componentes individuais.
📋 Inventário dos AFDs Implementados
Antes de iniciar a integração, preciso ter clareza absoluta sobre todos os AFDs que foram desenvolvidos nas semanas anteriores. Cada um destes autômatos foi cuidadosamente projetado para reconhecer uma categoria específica de tokens da linguagem Didágica:
AFDs Fundamentais Disponíveis
** AFD_1: Identificadores e Palavras-Chave Unificado**
Este AFD implementa a estratégia híbrida: reconhece a linguagem regular completa de identificadores válidos, seguida de classificação por tabela hash:
M_1 = (Q_1, \Sigma_1, \delta_1, q_{1,0}, F_1)
onde:
- Q_1 = \{q_{1,0}, q_{1,1}, ERRO_1\} - \Sigma_1 = \{a\text{-}z, A\text{-}Z, 0\text{-}9, \_, \text{acentos portugueses}\} - F_1 = \{q_{1,1}\} - Linguagem: L(M_1) = [a\text{-}z\text{á}\text{-}\text{ç}\_][a\text{-}z\text{á}\text{-}\text{ç}0\text{-}9\_]*
** AFD_2: Literais Numéricos Unificado**
Um AFD sofisticado que reconhece três tipos de literais numéricos: inteiros, decimais e científicos:
M_2 = (Q_2, \Sigma_2, \delta_2, q_{2,0}, F_2)
onde:
- Q_2 = \{q_{2,0}, q_{2,zero}, q_{2,nonzero}, q_{2,ponto\_zero}, q_{2,ponto\_nonzero}, q_{2,decimal},
q_{2,exp\_start}, q_{2,exp\_sinal}, q_{2,exp\_digito}, ERRO_2\} - \Sigma_2 = \{0\text{-}9, ., e, E, +, -\} - F_2 = \{q_{2,zero}, q_{2,nonzero}, q_{2,decimal}, q_{2,exp\_digito}\} - Linguagem: L(M_2) = L_{int} \cup L_{dec} \cup L_{sci}
** AFD_3: Literais de Texto (Strings)**
Reconhece strings delimitadas por aspas duplas com suporte a sequências de escape:
M_3 = (Q_3, \Sigma_3, \delta_3, q_{3,0}, F_3)
onde:
- Reconhece padrão: "([^"\\]|\\.)*" - Suporta escapes: \n, \t, \r, \\, \", \'
** AFD_4: Operadores Relacionais**
Reconhece operadores de comparação com precedência apropriada:
M_4 = (Q_4, \Sigma_4, \delta_4, q_{4,0}, F_4)
onde:
- \Sigma_4 = \{=, !, <, >\} - Linguagem: L(M_4) = \{==, !=, <, >, <=, >=\}
** AFD_5: Operadores Aritméticos**
Reconhece operadores aritméticos básicos:
M_5 = (Q_5, \Sigma_5, \delta_5, q_{5,0}, F_5)
onde:
- Linguagem: L(M_5) = \{+, -, *, /, \%\}
** AFD_6: Delimitadores e Pontuação**
Reconhece símbolos de pontuação e delimitadores:
M_6 = (Q_6, \Sigma_6, \delta_6, q_{6,0}, F_6)
onde:
- Linguagem: L(M_6) = \{(, ), \{, \}, [, ], ,, ;, .\}
** AFD_7: Comentários de Linha**
Reconhece comentários iniciados por # até o fim da linha:
M_7 = (Q_7, \Sigma_7, \delta_7, q_{7,0}, F_7)
onde:
- Linguagem: L(M_7) = \{\#\}(\Sigma \setminus \{newline\})^*
** AFD_8: Comentários de Bloco**
Reconhece comentários delimitados por /* e */:
M_8 = (Q_8, \Sigma_8, \delta_8, q_{8,0}, F_8)
onde:
- Linguagem: L(M_8) = \{/\}\{*\}\Sigma^*\{*\}\{/\}
** AFD_9: Whitespace**
Reconhece e descarta espaços em branco:
M_9 = (Q_9, \Sigma_9, \delta_9, q_{9,0}, F_9)
onde:
- Linguagem: L(M_9) = [\text{space}\text{ }\text{tab}\text{ }\text{newline}\text{ }\text{return}]^+
🔗 Estratégia de Integração: Construindo o AFN Unificado
A integração de múltiplos AFDs em um AFN unificado requer uma estratégia cuidadosamente planejada. Existem várias abordagens possíveis, cada uma com vantagens e desvantagens específicas. Após análise detalhada, escolhi a abordagem de estado inicial unificado com epsilon-transições, pois ela maximiza a modularidade e facilita manutenção futura.
Princípios da Integração
Preservação da Modularidade: Cada AFD original permanece conceitualmente intacto dentro do AFN unificado. Isso facilita debugging e permite modificações futuras em componentes individuais sem afetar outros.
Não-Determinismo Controlado: O não-determinismo é introduzido apenas no estado inicial, onde decidimos qual categoria de token tentar reconhecer. Uma vez dentro de um “módulo” específico, o processamento permanece determinístico.
Priorização Implícita: A ordem das epsilon-transições do estado inicial codifica prioridades entre diferentes categorias de tokens. Isso resolve ambiguidades de forma sistemática e previsível.
Decisões de Design Fundamentais
Decisão 1: Estado Inicial Unificado
Criarei um novo estado inicial q_0 que não pertence a nenhum AFD original. Deste estado, epsilon-transições conduzem aos estados iniciais de cada AFD:
\delta_{AFN}(q_0, \varepsilon) = \{q_{1,0}, q_{2,0}, q_{3,0}, q_{4,0}, q_{5,0}, q_{6,0}, q_{7,0}, q_{8,0}, q_{9,0}\}
Esta decisão permite que o AFN “tente” todas as categorias de tokens simultaneamente ao começar a processar uma nova sequência de caracteres.
Decisão 2: Preservação de Estados Originais
Todos os estados de cada AFD original são preservados no AFN unificado, com renomeação para evitar conflitos:
Q_{AFN} = \{q_0\} \cup Q_1 \cup Q_2 \cup Q_3 \cup Q_4 \cup Q_5 \cup Q_6 \cup Q_7 \cup Q_8 \cup Q_9
Esta preservação mantém a estrutura lógica de cada reconhecedor, facilitando compreensão e manutenção.
Decisão 3: Estados Finais Marcados por Categoria
Cada estado final do AFN unificado carrega informação sobre qual categoria de token foi reconhecida. Isso é implementado através de uma função de rotulação:
\lambda: F_{AFN} \rightarrow TiposToken
onde F_{AFN} = F_1 \cup F_2 \cup F_3 \cup F_4 \cup F_5 \cup F_6 \cup F_7 \cup F_8 \cup F_9
Decisão 4: Tratamento de Whitespace
Caracteres de whitespace são reconhecidos e descartados, mas não geram tokens. Estados finais de M_9 são marcados especialmente para indicar “reconhecido mas descartado”.
Decisão 5: Ordem de Prioridade para Ambiguidades
Quando múltiplos AFDs podem reconhecer a mesma string (por exemplo, palavras-chave vs. identificadores), a ordem das epsilon-transições estabelece prioridade:
- Literais de texto (maior prioridade - match explícito)
- Comentários (para não confundir com operadores)
- Operadores relacionais (antes de aritméticos para reconhecer
==,!=) - Operadores aritméticos
- Literais numéricos
- Identificadores/Palavras-chave (menor prioridade inicial)
- Delimitadores
- Whitespace (sempre descartado)
Esta ordenação garante que ambiguidades sejam resolvidas de forma previsível e consistente com a semântica da linguagem.
🎨 Construção Formal do AFN Unificado
Agora procedo à construção formal e sistemática do AFN unificado, documentando cada decisão e justificando cada escolha:
Definição Formal Completa
M_{AFN} = (Q_{AFN}, \Sigma_{AFN}, \delta_{AFN}, q_{0}, F_{AFN})
Conjunto de Estados:
Q_{AFN} = \{q_0\} \cup \bigcup_{i=1}^{9} Q_i
onde cada Q_i é o conjunto de estados do AFD correspondente. Para evitar conflitos de nomes, prefixamos cada estado com seu número de AFD: q_{i,j} denota o estado j do AFD i.
Alfabeto Unificado:
\Sigma_{AFN} = \bigcup_{i=1}^{9} \Sigma_i
Este é o alfabeto completo da linguagem Didágica, incluindo todos os caracteres que podem aparecer em qualquer token válido.
Estado Inicial:
q_0 - um novo estado criado especificamente para unificar todos os AFDs
Estados Finais com Rotulação:
F_{AFN} = \{(f, \lambda(f)) : f \in \bigcup_{i=1}^{9} F_i\}
onde \lambda mapeia cada estado final para o tipo de token correspondente.
Função de Transição Estendida:
A função de transição \delta_{AFN}: Q_{AFN} \times (\Sigma_{AFN} \cup \{\varepsilon\}) \rightarrow \mathcal{P}(Q_{AFN}) é definida por casos:
Epsilon-transições do estado inicial:
\delta_{AFN}(q_0, \varepsilon) = \{q_{1,0}, q_{2,0}, q_{3,0}, q_{4,0}, q_{5,0}, q_{6,0}, q_{7,0}, q_{8,0}, q_{9,0}\}
Transições dentro de cada AFD original (para 1 \leq i \leq 9):
\forall q \in Q_i, \forall a \in \Sigma_i: \delta_{AFN}(q, a) = \delta_i(q, a)
Nenhuma outra transição existe:
\forall q \in Q_{AFN} \setminus (\{q_0\} \cup \bigcup_{i=1}^{9} Q_i), \forall a \in \Sigma_{AFN} \cup \{\varepsilon\}: \delta_{AFN}(q, a) = \emptyset
Esta definição garante que o AFN unificado preserva completamente a funcionalidade de cada AFD individual enquanto permite processamento não-determinístico inicial.
🔄 Conversão de AFN para AFD: O Algoritmo de Construção de Subconjuntos
🎯 A Intuição Fundamental da Transformação
Antes de explorarmos os detalhes algorítmicos e as formalidades matemáticas, precisamos desenvolver uma intuição profunda sobre o que realmente significa converter um autômato finito não-determinístico em sua contraparte determinística. Esta compreensão intuitiva será o alicerce sobre o qual construiremos todo o conhecimento técnico subsequente.
Imagine que você está assistindo a um filme de suspense onde múltiplas linhas temporais alternativas se desenrolam simultaneamente na tela. O protagonista toma uma decisão e você vê três futuros possíveis acontecendo ao mesmo tempo, cada um explorando uma consequência diferente dessa escolha. O AFN funciona exatamente assim: ele pode estar explorando vários caminhos computacionais simultaneamente, mantendo múltiplas possibilidades ativas, tentando encontrar pelo menos um caminho que conduza à aceitação da string de entrada.
Em contraste, o AFD é como assistir a uma única linha temporal determinística, onde cada evento leva inexoravelmente a uma única consequência específica. Não há mistério, não há múltiplas possibilidades coexistindo. Cada símbolo de entrada processado resulta em uma transição única e bem definida para um estado específico. Esta previsibilidade torna os AFDs extremamente eficientes para implementação em computadores reais, mas como capturar todo o poder expressivo e a flexibilidade do não-determinismo dentro desta estrutura rígida?
A resposta que os teóricos da computação descobriram é simultaneamente simples e profundamente elegante: cada estado do AFD representará um conjunto de estados do AFN. Pense nisso como uma fotografia que congela todas as possibilidades simultâneas em um único instantâneo. Se após processar a string “ab” o AFN poderia estar simultaneamente nos estados q₁, q₂ e q₅, então o AFD terá um único estado que chamaremos {q₁, q₂, q₅}, representando precisamente essa configuração de múltiplas possibilidades. Cada estado-conjunto do AFD encapsula uma configuração completa possível do AFN, tornando explícito o que no AFN permanecia implícito através do não-determinismo.
💡 A Essência da Conversão
A conversão de AFN para AFD não adiciona nem remove poder computacional. Ambos reconhecem exatamente a mesma classe de linguagens, as linguagens regulares. O que a conversão faz é trocar a flexibilidade conceitual do não-determinismo pela previsibilidade e eficiência do determinismo. É uma transformação que preserva a funcionalidade enquanto otimiza a implementação prática.
Esta equivalência fundamental entre AFNs e AFDs tem consequências profundas. Ela nos permite usar a representação mais conveniente para cada fase do desenvolvimento de sistemas reais. Podemos projetar usando AFNs quando a clareza conceitual é primordial, e depois converter mecanicamente para AFDs quando a eficiência de execução se torna importante. O algoritmo de construção de subconjuntos é a ponte que torna esta flexibilidade possível.
📋 Visão Geral do Algoritmo de Construção de Subconjuntos
O algoritmo que estudaremos em profundidade é conhecido formalmente como Algoritmo de Construção de Subconjuntos, e informalmente como “powerset construction” na literatura de língua inglesa. Este nome deriva do fato de que, no pior caso teórico, o algoritmo pode precisar construir estados correspondentes a todos os subconjuntos possíveis do conjunto de estados do AFN original, que é exatamente o conjunto potência desse conjunto de estados.
O algoritmo recebe como entrada uma especificação completa de um AFN e produz como saída uma especificação equivalente de um AFD. Formalmente, a entrada é uma quíntupla M_{AFN} = (Q_{AFN}, \Sigma_{AFN}, \delta_{AFN}, q_0, F_{AFN}) representando o autômato finito não-determinístico, e a saída é outra quíntupla M_{AFD} = (Q_{AFD}, \Sigma_{AFD}, \delta_{AFD}, q_{0,AFD}, F_{AFD}) representando o autômato finito determinístico equivalente.
O processo de conversão pode ser compreendido como uma exploração sistemática de todas as configurações possíveis que o AFN pode assumir durante o processamento de strings. Para cada configuração identificada, criamos um estado correspondente no AFD. Para cada transição que o AFN pode realizar a partir dessa configuração, criamos uma transição correspondente no AFD. Este mapeamento metódico garante que o AFD resultante simula perfeitamente o comportamento do AFN original, mas sem nenhum não-determinismo.
🗺️ As Quatro Fases do Algoritmo
O algoritmo opera em quatro fases distintas e bem definidas. A primeira fase é a inicialização, onde preparamos todas as estruturas de dados necessárias e identificamos o estado inicial do AFD. A segunda fase é a construção iterativa, onde exploramos sistematicamente todas as transições possíveis e construímos novos estados conforme necessário. A terceira fase define quais dos estados construídos devem ser marcados como estados finais. A quarta fase documenta e formaliza o AFD resultante. Cada fase tem seu papel específico e todas são essenciais para a corretude do algoritmo.
Compreender a estrutura em fases do algoritmo não apenas facilita sua implementação, mas também ajuda na depuração quando algo não funciona conforme esperado. Se o AFD resultante aceita strings que deveria rejeitar, o problema provavelmente está na definição dos estados finais. Se ele rejeita strings que deveria aceitar, o problema pode estar na construção das transições ou no cálculo do epsilon-closure.
🏗️ Fase 1: Inicialização do AFD
A primeira fase do algoritmo de conversão estabelece o terreno sobre o qual todo o trabalho subsequente será construído. Aqui preparamos todas as estruturas de dados necessárias e identificamos o ponto de partida da exploração que virá nas fases seguintes. Esta fase é conceitualmente direta mas absolutamente essencial para a corretude do algoritmo.
Criando o Estado Inicial do AFD
O estado inicial do AFD não pode ser simplesmente o estado inicial do AFN. Lembre-se de que mesmo antes de ler qualquer símbolo de entrada, o AFN pode usar epsilon-transições para alcançar outros estados. Portanto, o estado inicial do AFD deve ser o epsilon-closure do estado inicial do AFN: q_{0,AFD} = \varepsilon\text{-CLOSURE}(\{q_0\}).
Esta escolha faz perfeito sentido quando pensamos na semântica do que o AFD está modelando. O AFD precisa começar em uma configuração que representa todas as possibilidades que o AFN teria antes de processar qualquer entrada. Se o AFN começa em q0 mas pode imediatamente saltar via epsilon para q1 e q2, então o AFD precisa começar em um estado representando {q0, q1, q2}.
📦 Estruturas de Dados Necessárias
Para implementar o algoritmo eficientemente, precisamos de três estruturas de dados principais que manteremos ao longo de todo o processo de conversão.
A primeira estrutura é o conjunto Q_AFD, que contém todos os estados do AFD que descobrimos até o momento. Inicialmente, este conjunto contém apenas o estado inicial que acabamos de calcular. À medida que exploramos transições, descobriremos novos estados-conjunto que adicionaremos a Q_AFD.
A segunda estrutura é a WorkList, uma fila ou pilha contendo estados do AFD que ainda precisam ser processados. Processare um estado significa examinar todas as suas possíveis transições para construir os estados destino. Inicialmente, a WorkList contém apenas o estado inicial. À medida que descobrimos novos estados, os adicionamos à WorkList. Quando a WorkList esvazia, significa que exploramos completamente o espaço de estados e o algoritmo termina.
A terceira estrutura é a função de transição δ_AFD, que inicialmente está vazia. Esta será gradualmente preenchida à medida que descobrimos as transições que conectam os estados do AFD. Cada transição descoberta é adicionada a esta estrutura, construindo incrementalmente a tabela de transições completa do AFD.
Definindo o Alfabeto do AFD
O alfabeto do AFD é derivado diretamente do alfabeto do AFN, mas com uma diferença sutil e importante: excluímos epsilon. Por definição, AFDs não têm epsilon-transições, então não faz sentido incluir epsilon no alfabeto. Formalmente, \Sigma_{AFD} = \Sigma_{AFN} \setminus \{\varepsilon\}.
Esta exclusão não perde informação porque o efeito das epsilon-transições está implicitamente capturado no epsilon-closure que aplicamos em vários pontos do algoritmo. Quando calculamos transições no AFD, sempre aplicamos epsilon-closure aos resultados, garantindo que os efeitos das epsilon-transições originais sejam preservados no comportamento do AFD resultante.
🔨 Fase 2: Construção Iterativa dos Estados
A segunda fase é onde a maior parte do trabalho computacional acontece. Aqui exploramos sistematicamente todas as transições possíveis do AFD, construindo novos estados conforme necessário e estabelecendo as conexões entre eles. Esta fase é o coração do algoritmo de construção de subconjuntos.
O Loop Principal de Exploração
O algoritmo funciona processando estados da WorkList um por um, em qualquer ordem (a ordem não afeta o resultado final, apenas a ordem em que estados são descobertos). Para cada estado S removido da WorkList, examinamos todas as transições possíveis a partir de S. Para cada símbolo a no alfabeto, calculamos qual deveria ser o estado destino δ_AFD(S, a). Se esse estado destino é novo (não foi descoberto anteriormente), adicionamos ele tanto a Q_AFD quanto à WorkList para ser processado posteriormente. Se o estado já existe, simplesmente adicionamos a transição sem criar duplicatas.
Este processo continua até que a WorkList esteja vazia, momento em que garantimos ter descoberto todos os estados alcançáveis a partir do estado inicial e todas as transições entre eles. A propriedade importante é que construímos apenas estados alcançáveis, não todos os subconjuntos possíveis de Q_AFN. Esta construção preguiçosa é o que torna o algoritmo prático, porque o número de estados alcançáveis é tipicamente muito menor que o limite teórico de 2^n estados.
🎯 Calculando Transições do AFD
Para um estado-conjunto S e um símbolo a, calcular o próximo estado T requer dois passos distintos mas relacionados. O primeiro passo é a função MOVE, e o segundo passo é a aplicação do epsilon-closure.
A função MOVE calcula para onde os estados individuais em S podem ir ao ler o símbolo a. Formalmente, \text{MOVE}(S, a) = \bigcup_{q \in S} \delta_{AFN}(q, a). Isso significa que para cada estado q no conjunto S, consultamos a função de transição do AFN para ver para quais estados q pode ir lendo a, e então fazemos a união de todos esses conjuntos destino.
Após calcular MOVE, aplicamos epsilon-closure ao resultado: T = \varepsilon\text{-CLOSURE}(\text{MOVE}(S, a)). Por que este segundo passo é necessário? Porque após fazer uma transição que consome o símbolo a, o AFN pode imediatamente fazer epsilon-transições adicionais. Para capturar completamente todos os estados que o AFN poderia alcançar, precisamos incluir todos os estados alcançáveis através dessas epsilon-transições subsequentes.
Exemplo Completo de Construção Passo a Passo
Vamos trabalhar um exemplo concreto e completo para ver o algoritmo em ação. Consideraremos um AFN que reconhece strings sobre o alfabeto {a, b} que contêm a substring “ab”. O AFN tem três estados {q0, q1, q2}, onde q0 é o estado inicial e q2 é o único estado final. As transições do AFN são: δ(q0, a) = {q0, q1} (ao ler ‘a’, pode permanecer em q0 ou avançar para q1), δ(q0, b) = {q0} (ao ler ‘b’, permanece em q0), δ(q1, b) = {q2} (ao ler ‘b’ após ter lido ‘a’, vai para q2), e q2 tem auto-loops para ambos ‘a’ e ‘b’: δ(q2, a) = {q2} e δ(q2, b) = {q2}.
Assumindo que não há epsilon-transições neste AFN, o estado inicial do AFD é S₀ = {q0}. Adicionamos S₀ a Q_AFD e à WorkList, e começamos o loop principal.
Na primeira iteração, removemos S₀ = {q0} da WorkList e processamos as transições para cada símbolo. Para o símbolo ‘a’, calculamos MOVE(S₀, a) = δ(q0, a) = {q0, q1}. Aplicando epsilon-closure (que neste caso não faz nada porque não há epsilon-transições), obtemos T_a = {q0, q1}. Este é um novo estado, então criamos S₁ = {q0, q1}, adicionamos ele a Q_AFD e à WorkList, e definimos δ_AFD(S₀, a) = S₁. Para o símbolo ‘b’, calculamos MOVE(S₀, b) = δ(q0, b) = {q0}, que resulta no próprio S₀. Definimos δ_AFD(S₀, b) = S₀ (um auto-loop).
Na segunda iteração, removemos S₁ = {q0, q1} da WorkList. Para o símbolo ‘a’, calculamos MOVE(S₁, a). Precisamos consultar δ(q0, a) e δ(q1, a). Obtemos δ(q0, a) = {q0, q1} e δ(q1, a) = ∅ (não há transição). A união resulta em {q0, q1}, que é o próprio S₁. Definimos δ_AFD(S₁, a) = S₁ (auto-loop). Para o símbolo ‘b’, calculamos MOVE(S₁, b) = δ(q0, b) ∪ δ(q1, b) = {q0} ∪ {q2} = {q0, q2}. Este é um novo estado, então criamos S₂ = {q0, q2}, adicionamos ele a Q_AFD e à WorkList, e definimos δ_AFD(S₁, b) = S₂.
Na terceira iteração, removemos S₂ = {q0, q2} da WorkList. Para o símbolo ‘a’, calculamos MOVE(S₂, a) = δ(q0, a) ∪ δ(q2, a) = {q0, q1} ∪ {q2} = {q0, q1, q2}. Este é um novo estado, então criamos S₃ = {q0, q1, q2}, adicionamos ele a Q_AFD e à WorkList, e definimos δ_AFD(S₂, a) = S₃. Para o símbolo ‘b’, calculamos MOVE(S₂, b) = δ(q0, b) ∪ δ(q2, b) = {q0} ∪ {q2} = {q0, q2} = S₂. Definimos δ_AFD(S₂, b) = S₂ (auto-loop).
Na quarta e última iteração, removemos S₃ = {q0, q1, q2} da WorkList. Para ‘a’, calculamos MOVE(S₃, a) = δ(q0, a) ∪ δ(q1, a) ∪ δ(q2, a) = {q0, q1} ∪ ∅ ∪ {q2} = {q0, q1, q2} = S₃. Auto-loop. Para ‘b’, calculamos MOVE(S₃, b) = {q0} ∪ {q2} ∪ {q2} = {q0, q2} = S₂. Definimos δ_AFD(S₃, b) = S₂. A WorkList agora está vazia, então a construção está completa.
🎯 Fase 3: Definindo Estados Finais do AFD
A terceira fase determina quais dos estados-conjunto que construímos devem ser marcados como estados finais no AFD resultante. Esta fase é conceitualmente simples mas absolutamente essencial para preservar a semântica de aceitação do AFN original.
A Regra de Aceitação
A regra para determinar se um estado-conjunto S do AFD deve ser final é elegante e intuitiva: S é final se e somente se S contém pelo menos um estado final do AFN original. Formalmente, F_{AFD} = \{S \in Q_{AFD} : S \cap F_{AFN} \neq \emptyset\}.
Por que esta regra está correta? Pense na semântica do que significa o AFN aceitar uma string. O AFN aceita se existe pelo menos um caminho computacional que leva a um estado final. No AFD, cada estado-conjunto representa uma configuração possível do AFN, ou seja, um conjunto de estados onde o AFN poderia estar simultaneamente. Se essa configuração inclui um estado final do AFN, significa que existe um caminho que leva à aceitação, portanto o AFD deve aceitar nesse ponto.
✅ Aplicando a Regra ao Exemplo
Vamos aplicar esta regra ao AFD que construímos no exemplo anterior. O AFN original tinha F_AFN = {q2} como único estado final. Agora examinamos cada estado do AFD que construímos para determinar se deve ser final.
Para S₀ = {q0}, verificamos se q2 pertence a S₀. Como q2 ∉ S₀, este estado não é final. Para S₁ = {q0, q1}, verificamos se q2 pertence a S₁. Como q2 ∉ S₁, este estado também não é final. Para S₂ = {q0, q2}, verificamos e descobrimos que q2 ∈ S₂. Portanto, S₂ é um estado final. Para S₃ = {q0, q1, q2}, também verificamos que q2 ∈ S₃, então S₃ também é final.
O conjunto de estados finais do AFD é portanto F_AFD = {S₂, S₃} = {{q0, q2}, {q0, q1, q2}}. Estes são exatamente os estados que representam configurações onde o AFN teria alcançado aceitação.
📊 Fase 4: Formalização e Documentação Completa
A quarta e última fase consolida todo o trabalho realizado nas fases anteriores em uma especificação formal completa e bem documentada do AFD resultante. Esta fase não apenas completa o algoritmo, mas também produz uma documentação que será valiosa para compreensão, verificação e uso futuro do autômato.
Especificação Formal Completa
Compilamos todos os componentes que construímos em uma quíntupla formal que define completamente o AFD. Para o exemplo que trabalhamos, a especificação completa é: M_{AFD} = (Q_{AFD}, \Sigma_{AFD}, \delta_{AFD}, q_{0,AFD}, F_{AFD}).
O conjunto de estados é Q_AFD = {{q0}, {q0, q1}, {q0, q2}, {q0, q1, q2}}. Para simplificar referências futuras, é comum renomear estes estados com nomes mais curtos: A = {q0}, B = {q0, q1}, C = {q0, q2}, D = {q0, q1, q2}. Portanto, Q_AFD = {A, B, C, D}.
O alfabeto é Σ_AFD = {a, b}, idêntico ao alfabeto do AFN original (excluindo epsilon, se houvesse). O estado inicial é q₀,AFD = A = {q0}. Os estados finais são F_AFD = {C, D} = {{q0, q2}, {q0, q1, q2}}.
A função de transição δ_AFD é melhor apresentada em formato tabular para clareza e facilidade de consulta. Esta tabela documenta todas as transições que descobrimos durante a fase de construção iterativa.
---
config:
theme: base
themeVariables:
primaryColor: "#e3f2fd"
primaryTextColor: "#1565c0"
primaryBorderColor: "#1976d2"
lineColor: "#1976d2"
secondaryColor: "#f3e5f5"
tertiaryColor: "#e8f5e8"
---
stateDiagram-v2
[*] --> A
A --> B: a
A --> A: b
B --> B: a
B --> C: b
C --> D: a
C --> C: b
D --> D: a
D --> C: b
C --> [*]
D --> [*]
note right of C
Estados finais: C e D
Contêm q2 do AFN
end note
Tabela de Transições do AFD
A função de transição pode ser visualizada claramente através de uma tabela onde as linhas representam os estados atuais e as colunas representam os símbolos de entrada. Cada célula contém o estado destino correspondente.
| Estado | a | b |
|---|---|---|
| A | B | A |
| B | B | C |
| C | D | C |
| D | D | C |
Esta tabela documenta completamente o comportamento do AFD. Por exemplo, a linha para o estado B nos diz que ao ler ‘a’, o AFD permanece em B (fazendo um auto-loop), e ao ler ‘b’, o AFD transita para C. Esta representação tabular é especialmente útil para implementação, pois pode ser diretamente codificada como uma estrutura de dados bidimensional em praticamente qualquer linguagem de programação.
🎨 Aplicação do Algoritmo ao AFN Unificado da Linguagem Didagica
Aplicação do Algoritmo ao AFN Unificado
Agora aplico sistematicamente o algoritmo de construção de subconjuntos ao AFN unificado da linguagem Didágica, documentando cada passo e cada decisão:
Fase 1: Estado Inicial do AFD
Cálculo do estado inicial:
q_{0,AFD} = \varepsilon\text{-}CLOSURE(\{q_0\}) = \{q_0, q_{1,0}, q_{2,0}, q_{3,0}, q_{4,0}, q_{5,0}, q_{6,0}, q_{7,0}, q_{8,0}, q_{9,0}\}
Interpretação: O estado inicial do AFD representa “todas as possibilidades que o AFN poderia estar explorando antes de ler qualquer caractere”. Como temos epsilon-transições do estado inicial para todos os nove AFDs componentes, o estado inicial do AFD contém todos esses estados.
Notação simplificada: Por conveniência, denotarei este estado como S_0 = \{q_0, q_{1,0}, \ldots, q_{9,0}\}.
Fase 2: Expansão Sistemática - Primeira Iteração
Vou processar S_0 para cada símbolo relevante do alfabeto. Como o alfabeto é grande, focarei nos símbolos mais representativos e depois generalizarei:
Processando dígito ‘0’ a partir de S_0
Transições no AFN:
- q_{2,0} \xrightarrow{0} q_{2,zero} (AFD de números reconhece ‘0’) - Nenhum outro estado em S_0 tem transição para ‘0’
Novo conjunto:
T_0 = \varepsilon\text{-}CLOSURE(\{q_{2,zero}\}) = \{q_{2,zero}\}
(Não há epsilon-transições saindo de q_{2,zero})
Definição de transição:
\delta_{AFD}(S_0, 0) = T_0 = \{q_{2,zero}\}
Análise: Ao ler ‘0’, o AFD move-se para um estado que representa “reconhecendo um número que começou com zero”. Este estado é final (reconhece o inteiro “0”) mas também tem transições para ponto decimal.
Processando dígito ‘1’ (representante de [1-9]) a partir de S_0
Transições no AFN:
- q_{2,0} \xrightarrow{1} q_{2,nonzero} (AFD de números) - Nenhum outro estado processa ‘1’ do estado inicial
Novo conjunto:
T_1 = \varepsilon\text{-}CLOSURE(\{q_{2,nonzero}\}) = \{q_{2,nonzero}\}
Definição de transição:
\delta_{AFD}(S_0, 1) = T_1 = \{q_{2,nonzero}\}
Generalização: O mesmo ocorre para ‘2’, ‘3’, …, ‘9’. Podemos otimizar o AFD agrupando esses casos.
Processando letra ‘a’ (representante de [a-z]) a partir de S_0
Transições no AFN:
- q_{1,0} \xrightarrow{a} q_{1,1} (AFD de identificadores) - Nenhum outro estado processa ‘a’ do estado inicial
Novo conjunto:
T_a = \varepsilon\text{-}CLOSURE(\{q_{1,1}\}) = \{q_{1,1}\}
Definição de transição:
\delta_{AFD}(S_0, a) = T_a = \{q_{1,1}\}
Análise: Ao ler uma letra minúscula, o AFD move-se para estado que reconhece identificadores. Este estado é final (identificador de uma letra é válido) e tem transições para continuar o identificador.
Processando símbolo ‘“’ a partir de S_0
Transições no AFN:
- q_{3,0} \xrightarrow{"} q_{3,dentro} (AFD de strings)
Novo conjunto:
T_{string} = \varepsilon\text{-}CLOSURE(\{q_{3,dentro}\}) = \{q_{3,dentro}\}
Definição de transição:
\delta_{AFD}(S_0, ") = T_{string} = \{q_{3,dentro}\}
Processando símbolo ‘+’ a partir de S_0
Transições no AFN:
- q_{5,0} \xrightarrow{+} q_{5,mais} (AFD de operadores aritméticos)
Novo conjunto:
T_{mais} = \varepsilon\text{-}CLOSURE(\{q_{5,mais}\}) = \{q_{5,mais}\}
Definição de transição:
\delta_{AFD}(S_0, +) = T_{mais} = \{q_{5,mais}\}
Análise: O estado \{q_{5,mais}\} é final, reconhecendo o operador ‘+’ completo.
Processando símbolo ‘=’ a partir de S_0
Transições no AFN:
- q_{4,0} \xrightarrow{=} q_{4,igual} (AFD de operadores relacionais)
Novo conjunto:
T_{igual} = \varepsilon\text{-}CLOSURE(\{q_{4,igual}\}) = \{q_{4,igual}\}
Definição de transição:
\delta_{AFD}(S_0, =) = T_{igual} = \{q_{4,igual}\}
Análise crítica: Este estado é final (reconhece ‘=’ como operador de atribuição), mas também tem transição para ‘=’ (reconhecendo ‘==’). Esta é uma decisão de design importante: o AFD precisa implementar a regra do “match mais longo”.
Processando símbolo ‘#’ a partir de S_0
Transições no AFN:
- q_{7,0} \xrightarrow{\#} q_{7,hash} (AFD de comentários de linha)
Novo conjunto:
T_{coment} = \varepsilon\text{-}CLOSURE(\{q_{7,hash}\}) = \{q_{7,hash}\}
Definição de transição:
\delta_{AFD}(S_0, \#) = T_{coment} = \{q_{7,hash}\}
Fase 3: Estados Gerados e Tabela de Transições Parcial
Após processar S_0 para todos os símbolos relevantes, temos:
Estados do AFD criados até agora:
- S_0 = \{q_0, q_{1,0}, q_{2,0}, q_{3,0}, q_{4,0}, q_{5,0}, q_{6,0}, q_{7,0}, q_{8,0}, q_{9,0}\} - T_0 = \{q_{2,zero}\} - T_1 = \{q_{2,nonzero}\} (e similares para 2-9) - T_a = \{q_{1,1}\} (e similares para outras letras) - T_{string} = \{q_{3,dentro}\} - T_{mais} = \{q_{5,mais}\} - T_{igual} = \{q_{4,igual}\} - T_{coment} = \{q_{7,hash}\} - … (e outros para delimitadores, operadores, etc.)
Observação: Muitos destes estados são singleton sets (contêm apenas um estado do AFN). Isto ocorre porque, após a escolha não-determinística inicial, cada “módulo” AFD opera deterministicamente.
Fase 4: Processamento de Estados Subsequentes
Agora preciso processar cada novo estado criado. Vou demonstrar o processamento de alguns estados representativos:
Processando T_1 = \{q_{2,nonzero}\}
Este estado representa “reconhecendo um número que começou com dígito não-zero”.
Para dígitos [0-9]:
- q_{2,nonzero} \xrightarrow{0\text{-}9} q_{2,nonzero}
\delta_{AFD}(T_1, d) = \{q_{2,nonzero}\} = T_1 para d \in \{0,1,\ldots,9\}
Para ponto ‘.’:
- q_{2,nonzero} \xrightarrow{.} q_{2,ponto\_nonzero}
\delta_{AFD}(T_1, .) = \{q_{2,ponto\_nonzero}\} = T_{decimal\_init} (novo estado)
Para ‘e’ ou ‘E’:
- q_{2,nonzero} \xrightarrow{e/E} q_{2,exp\_start}
\delta_{AFD}(T_1, e) = \{q_{2,exp\_start}\} = T_{exp\_init} (novo estado)
Estados finais: T_1 é estado final, pois q_{2,nonzero} \in F_{AFN} (reconhece inteiro válido).
Processando T_a = \{q_{1,1}\}
Este estado representa “reconhecendo um identificador”.
Para letras minúsculas, dígitos, underscore:
- q_{1,1} \xrightarrow{[a\text{-}z0\text{-}9\_]} q_{1,1}
\delta_{AFD}(T_a, c) = \{q_{1,1}\} = T_a para c \in [a\text{-}z0\text{-}9\_]
Análise: Este estado tem self-loop, permitindo identificadores de qualquer comprimento.
Estados finais: T_a é estado final, pois q_{1,1} \in F_{AFN} (reconhece identificador válido).
Processando T_{igual} = \{q_{4,igual}\}
Este estado representa “reconheceu ‘=’ e pode ser atribuição ou início de ‘==’”.
Para ‘=’:
- q_{4,igual} \xrightarrow{=} q_{4,igual\_duplo}
\delta_{AFD}(T_{igual}, =) = \{q_{4,igual\_duplo}\} = T_{igualdade} (novo estado)
Para qualquer outro símbolo: Não há transição definida (implicitamente vai para estado de erro).
Estados finais: T_{igual} é estado final (reconhece ‘=’ como atribuição), mas T_{igualdade} também será final (reconhece ‘==’ como comparação).
Implementação da regra do match mais longo: O analisador léxico tentará ler ‘==’ se possível, caso contrário aceita ‘=’.
Fase 5: Tratamento de Ambiguidades no AFD
Um aspecto fundamental da conversão é como ambiguidades são resolvidas no AFD resultante. Vários cenários requerem atenção especial:
Ambiguidade 1: Identificadores vs Palavras-Chave
Problema: A string “guarde” é reconhecida pelo mesmo caminho que qualquer identificador.
Solução: Esta ambiguidade já foi resolvida na arquitetura híbrida:
1. O AFD reconhece “guarde” como identificador válido 2. Estado final carrega metadado indicando “consultar tabela hash” 3. Tabela hash determina classificação final: PALAVRA_CHAVE
No AFD: Estados finais derivados de F_1 (estados finais do AFD de identificadores) são marcados com rótulo especial “REQUER_CLASSIFICACAO_HASH”.
Ambiguidade 2: Operadores de Um vs Dois Caracteres
Problema: ‘=’ pode ser atribuição ou início de ‘==’, ‘<’ pode ser comparação ou início de ‘<=’, etc.
Solução implementada: Princípio do match mais longo:
1. Estados intermediários (como T_{igual} = \{q_{4,igual}\}) são marcados como finais 2. Mas o algoritmo de scanning continua enquanto houver transições válidas 3. Apenas quando não há transição válida, o último estado final alcançado é usado
Implementação no analisador léxico:
ultimo_estado_final = null
posicao_ultimo_final = -1
ENQUANTO há caracteres FAÇA:
ler próximo caractere
tentar transição
SE transição válida ENTÃO:
avançar estado
SE estado_atual é final ENTÃO:
ultimo_estado_final = estado_atual
posicao_ultimo_final = posicao_atual
FIM SE
SENÃO:
SE ultimo_estado_final ≠ null ENTÃO:
retroceder para posicao_ultimo_final
emitir token baseado em ultimo_estado_final
SUCESSO
SENÃO:
ERRO
FIM SE
FIM SE
FIM ENQUANTOAmbiguidade 3: Ponto Decimal vs Delimitador
Problema: O símbolo ‘.’ pode ser:
- Delimitador (acesso a membro, fim de sentença) - Parte de número decimal (3.14) - Início de decimal sem parte inteira (.5)
Solução: Ordem de prioridade e contexto:
1. Se estado ativo contém q_{2,nonzero} ou q_{2,zero}, ‘.’ é interpretado como decimal 2. Caso contrário, ‘.’ é delimitador
No AFD: Estados que contêm estados do AFD de números têm precedência para processar ‘.’.
Fase 6: Contagem e Características do AFD Resultante
Após aplicar o algoritmo completo, o AFD resultante tem as seguintes características:
Número de estados: Embora teoricamente possa ter até 2^{|Q_{AFN}|} estados, na prática terá significativamente menos devido à estrutura modular do AFN:
|Q_{AFD}| \approx |Q_1| + |Q_2| + \ldots + |Q_9| + \text{estados de transição}
Estimativa: Aproximadamente 50-70 estados (muito menos que o limite teórico de 2^{81} se o AFN tivesse 81 estados).
Estados singleton: A maioria dos estados do AFD são singleton sets, contendo apenas um estado do AFN. Apenas o estado inicial contém múltiplos estados.
Estrutura da função de transição: Extremamente esparsa. Cada estado tem transições definidas apenas para um pequeno subconjunto do alfabeto.
Estados finais: Aproximadamente 20-25 estados finais, correspondendo aos diferentes tipos de tokens que podem ser reconhecidos.
📊 Diagrama Completo do AFD Resultante
Devido à complexidade do AFD completo, apresento uma visualização em múltiplas partes, focando em módulos específicos:
Módulo de Reconhecimento de Números no AFD
stateDiagram-v2
direction LR
[*] --> S0
S0 --> S_zero : 0
S0 --> S_nonzero : [1-9]
S_zero --> S_ponto_zero : .
S_nonzero --> S_nonzero : [0-9]
S_nonzero --> S_ponto_nonzero : .
S_ponto_zero --> S_decimal : [0-9]
S_ponto_nonzero --> S_decimal : [0-9]
S_decimal --> S_decimal : [0-9]
S_nonzero --> S_exp_start : [eE]
S_decimal --> S_exp_start : [eE]
S_exp_start --> S_exp_sinal : [+-]
S_exp_start --> S_exp_digito : [0-9]
S_exp_sinal --> S_exp_digito : [0-9]
S_exp_digito --> S_exp_digito : [0-9]
S_zero --> [*]
S_nonzero --> [*]
S_decimal --> [*]
S_exp_digito --> [*]
note right of S_zero
Estado final
Token: INTEIRO (valor 0)
end note
note right of S_nonzero
Estado final
Token: INTEIRO
end note
note right of S_decimal
Estado final
Token: DECIMAL
end note
note right of S_exp_digito
Estado final
Token: CIENTIFICO
end note
Módulo de Reconhecimento de Identificadores/Palavras-Chave no AFD
stateDiagram-v2
direction LR
[*] --> S0
S0 --> S_ident : [a-z_áçõ]
S_ident --> S_ident : [a-z0-9_áçõ]
S_ident --> [*]
note right of S_ident
Estado final
Token: IDENTIFICADOR*
*Requer classificação hash
para distinguir palavras-chave
end note
Módulo de Operadores Relacionais no AFD
stateDiagram-v2
direction LR
[*] --> S0
S0 --> S_igual_1 : =
S_igual_1 --> S_igual_2 : =
S0 --> S_menor : <
S_menor --> S_menor_igual : =
S0 --> S_maior : >
S_maior --> S_maior_igual : =
S0 --> S_excl : !
S_excl --> S_diferente : =
S_igual_1 --> [*]
S_igual_2 --> [*]
S_menor --> [*]
S_menor_igual --> [*]
S_maior --> [*]
S_maior_igual --> [*]
S_diferente --> [*]
note right of S_igual_1
Estado final
Token: ATRIBUICAO (=)
end note
note right of S_igual_2
Estado final
Token: IGUALDADE (==)
end note
note right of S_menor
Estado final
Token: MENOR (<)
end note
note right of S_menor_igual
Estado final
Token: MENOR_IGUAL (<=)
end note
Tabela de Transições Parcial do AFD
Para complementar os diagramas, apresento uma tabela de transições representativa:
| Estado | ‘0’ | ‘1-9’ | ‘a-z’ | ‘=’ | ‘<’ | ‘.’ | ‘“’ | ‘#’ | espaço |
|---|---|---|---|---|---|---|---|---|---|
| S_0 | S_{zero} | S_{nonzero} | S_{ident} | S_{=1} | S_{<} | S_{ponto} | S_{str} | S_{\#} | S_{ws} |
| S_{zero} | ∅ | ∅ | ∅ | ∅ | ∅ | S_{.0} | ∅ | ∅ | ∅ |
| S_{nonzero} | S_{nonzero} | S_{nonzero} | ∅ | ∅ | ∅ | S_{.nz} | ∅ | ∅ | ∅ |
| S_{ident} | S_{ident} | S_{ident} | S_{ident} | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ |
| S_{=1} | ∅ | ∅ | ∅ | S_{=2} | ∅ | ∅ | ∅ | ∅ | ∅ |
| S_{<} | ∅ | ∅ | ∅ | S_{<=} | ∅ | ∅ | ∅ | ∅ | ∅ |
Legenda:
- ∅ indica que não há transição definida (implicitamente rejeita ou retrocede) - Estados em negrito são estados finais - Estados marcados com * requerem processamento adicional (hash lookup)
🎯 Análise de Complexidade e Eficiência
Complexidade da Conversão AFN → AFD
Complexidade temporal: O(2^{|Q_{AFN}|} \times |\Sigma_{AFN}|) no pior caso teórico.
Complexidade prática: O(k \times |\Sigma_{AFN}|) onde k é o número de estados realmente construídos (muito menor que 2^{|Q_{AFN}|}).
Complexidade espacial: O(k) para armazenar os estados construídos.
Justificativa da eficiência prática: A estrutura modular do AFN garante que poucos estados-conjunto são realmente alcançáveis, resultando em complexidade linear na prática.
Eficiência do AFD Resultante
Tempo de reconhecimento: O(n) onde n é o comprimento da entrada (linear e ótimo).
Memória: O(1) durante execução (apenas estado atual).
Armazenamento: O(|Q_{AFD}| \times |\Sigma_{AFD}|) para tabela de transições.
Otimizações possíveis:
1. Compressão da tabela: Muitas transições são undefined; use representação esparsa 2. Minimização: Aplicar algoritmo de minimização pode reduzir ainda mais o número de estados 3. Code generation: Para AFD pequenos, gerar código direto em vez de usar tabela
🔍 Aplicações Práticas e Integração com Análise Léxica
Os conceitos que você dominou sobre AFNs encontram aplicação imediata e fundamental na análise léxica, a primeira fase de qualquer compilador. Compreender como AFNs se integram com esta aplicação prática consolida o aprendizado teórico e demonstra a relevância dos conceitos abstratos.
Design Modular de Analisadores Léxicos
A abordagem tradicional para análise léxica envolve especificar tokens usando expressões regulares e depois converter cada expressão para um AFD separado. Esta abordagem funciona, mas pode ser ineficiente quando muitos tokens compartilham prefixos comuns.
A abordagem baseada em AFNs permite uma estratégia mais elegante: construir AFNs separados para cada tipo de token, combiná-los em um AFN unificado usando não-determinismo, e depois converter o resultado para um AFD único otimizado.
graph TD
subgraph "Design Modular com AFNs"
A[Identificadores] --> D[AFN Unificado]
B[Números] --> D
C[Operadores] --> D
D --> E[Conversão AFN→AFD]
E --> F[AFD Otimizado]
end
subgraph "Vantagens"
G[Especificação Clara]
H[Manutenibilidade]
I[Eficiência]
end
F --> G
F --> H
F --> I
style D fill:#e8f5e8
style F fill:#90EE90
Tratamento de Ambiguidades e Prioridades
Quando múltiplos padrões podem reconhecer a mesma string (como palavras-chave versus identificadores), o não-determinismo dos AFNs oferece uma forma natural de expressar esta ambiguidade, que depois pode ser resolvida durante a conversão para AFD usando regras de prioridade apropriadas.
💡 Estratégias de Resolução de Conflitos
Prioridade por ordem: Tokens especificados primeiro têm prioridade sobre tokens especificados depois
Regra do prefixo mais longo: Entre múltiplas possibilidades, escolha aquela que consome mais caracteres da entrada
Prioridade explícita: Associe níveis de prioridade numéricos a diferentes classes de tokens
Contexto local: Use lookahead limitado para resolver ambiguidades baseadas em contexto imediato
Otimizações Específicas para Análise Léxica
A natureza específica da análise léxica permite otimizações que vão além dos algoritmos gerais de AFNs:
Minimização especializada: Aproveite o fato de que analisadores léxicos frequentemente processam caracteres ASCII para usar representações mais compactas de tabelas de transição.
Compilação de código: Para padrões simples, gere código especializado em vez de usar tabelas de transição, resultando em performance superior.
Processamento em lote: Para análise de arquivos grandes, processe múltiplos caracteres simultaneamente quando padrões permitem.
🎨 Visualização e Debugging de AFNs
Trabalhar efetivamente com AFNs requer desenvolver intuição sobre seu comportamento e ferramentas para debug quando eles não funcionam como esperado. A visualização é fundamental para este processo.
Técnicas de Visualização
Diagramas de estados: Represente estados como nós e transições como arestas, usando cores diferentes para destacar estados finais e caminhos de aceitação.
Árvores de execução: Para palavras específicas, mostre como o conjunto de estados ativos evolui durante o processamento, revelando o comportamento não-determinístico.
Análise de cobertura: Identifique estados e transições que nunca são exercitados pelos seus casos de teste, sugerindo lacunas na validação ou componentes desnecessários.
graph TB
subgraph "Debugging AFN - Palavra 'aab'"
A["Passo 0: {q0}"] --> B["Passo 1 (a): {q0,q1,q3}"]
B --> C["Passo 2 (a): {q0,q1,q3}"]
C --> D["Passo 3 (b): {q0,q2,q4}"]
E["Estado q2: ACEITA"]
F["Estado q4: ACEITA"]
D --> E
D --> F
end
style A fill:#e3f2fd
style B fill:#fff3e0
style C fill:#fff3e0
style D fill:#90EE90
style E fill:#FFD700
style F fill:#FFD700
Debugging Sistemático
Validação incremental: Teste cada componente do AFN separadamente antes de integrá-los, facilitando isolamento de problemas.
Casos de teste abrangentes: Desenvolva casos que exercitem todas as transições e combinações de estados, incluindo casos extremos.
Instrumentação de execução: Adicione logging para rastrear evolução do conjunto de estados ativos durante processamento de casos problemáticos.
💡 Resumo Prático
AFNs são usados para:
✅ Design e especificação de analisadores léxicos
✅ Prototipagem rápida de novos recursos linguísticos
✅ Geração automática de código otimizado
✅ Resolução elegante de ambiguidades lexicais
✅ Implementação de recursos avançados (comentários aninhados, strings complexas)
✅ Desenvolvimento de DSLs e linguagens especializadas
AFNs NÃO são usados para:
❌ Implementação final de alta performance (usa-se AFDs)
❌ Análise sintática (usa-se parsers específicos)
❌ Análise semântica (usa-se outras técnicas)
Em essência, AFNs são a linguagem de design dos compiladores - permitem expressar ideias complexas de forma clara e natural, que depois são convertidas automaticamente para implementações eficientes! 🌟
🌊 Reflexões sobre o Não-Determinismo e Preparação para a Próxima Semana
O estudo dos autômatos finitos não-determinísticos representa um marco importante na sua jornada através da teoria da computação. Você descobriu como conceitos aparentemente paradoxais podem ser formalizados matematicamente e aplicados para resolver problemas práticos de forma elegante.
🎓 Síntese dos Aprendizados Fundamentais
Flexibilidade conceitual: AFNs demonstram como relaxar restrições aparentemente fundamentais (determinismo) pode simplificar dramaticamente a especificação de algoritmos complexos.
Equivalência surpreendente: A descoberta de que não-determinismo não adiciona poder computacional, apenas conveniência de design, revela aspectos profundos sobre a natureza da computação.
Ponte entre teoria e prática: A conversão sistemática entre AFNs e AFDs ilustra como insights teóricos se materializam em algoritmos práticos eficientes.
Fundação para conceitos avançados: O não-determinismo que você dominou aqui reaparecerá em contextos mais sofisticados ao longo da disciplina.
O não-determinismo como ferramenta de design permite separar claramente a lógica de reconhecimento das preocupações de implementação eficiente. Esta separação de responsabilidades é um princípio fundamental do design de software que você aplicará repetidamente em sua carreira.
A construção sistemática de autômatos a partir de componentes menores demonstra a potência da abordagem compositional para resolver problemas complexos. Esta metodologia se estende muito além de autômatos, aparecendo em arquitetura de software, design de sistemas, e resolução de problemas em geral.
A equivalência entre diferentes representações (AFDs, AFNs, expressões regulares) exemplifica um tema recorrente na ciência da computação: múltiplas perspectivas sobre o mesmo fenômeno fundamental, cada uma oferecendo insights únicos e vantagens práticas específicas.
Antecipando Propriedades de Linguagens Regulares
Na próxima semana, você investigará as propriedades fundamentais das linguagens regulares - tanto suas capacidades impressionantes quanto suas limitações surpreendentes. Os AFNs que você dominou hoje serão ferramentas essenciais para estas investigações.
🔬 Preparando-se para Análise Profunda
Teoremas de fechamento: Você descobrirá que linguagens regulares são fechadas sob operações como união, concatenação, e complemento. AFNs fornecem construções elegantes para provar estes resultados.
Pumping lemma: Esta ferramenta poderosa para provar que certas linguagens não são regulares depende essencialmente da compreensão de como AFDs processam palavras longas.
Algoritmos de decisão: Questões como “duas linguagens regulares são iguais?” têm respostas algorítmicas que utilizam técnicas que você está desenvolvendo.
Limitações fundamentais: Compreender o que linguagens regulares não podem expressar é tão importante quanto conhecer suas capacidades.
A transição para propriedades teóricas representará uma mudança de foco da construção para a análise. Enquanto esta semana enfatizou como construir e converter autômatos, a próxima explorará questões mais profundas sobre o que estes modelos podem e não podem fazer.
As ferramentas que você desenvolveu - construção de AFNs, conversão para AFDs, análise de equivalência - se tornarão os instrumentos que você usará para investigar questões teóricas fundamentais sobre a natureza da computação regular.
A perspectiva prática permanecerá central mesmo durante análise teórica. Cada propriedade que você estudar terá implicações diretas para design de compiladores, processamento de texto, e desenvolvimento de algoritmos eficientes.
💫 A Jornada Continua: Reflexões Finais
Nesta semana, você dominou uma das técnicas mais poderosas da teoria da computação: a capacidade de transformar especificações não-determinísticas elegantes em implementações determinísticas eficientes. Você viu como múltiplos AFDs podem ser orquestrados através de um AFN unificado, e como o algoritmo de construção de subconjuntos converte sistematicamente esse AFN em um AFD equivalente.
O AFN unificado que construímos para a linguagem Didagica serve como modelo arquitetural, demonstrando clareza conceitual através de epsilon-transições modulares. O AFD resultante da conversão captura toda a funcionalidade do AFN em uma estrutura determinística pronta para implementação eficiente.
Na próxima semana, você aplicará propriedades de fechamento e o pumping lemma para validar teoricamente as decisões de design que tomou. Na Semana 8, verá como todo este trabalho teórico se materializa em código executável, transformando o AFD em um analisador léxico robusto e eficiente que processa código fonte real.
A ponte entre teoria e prática está quase completa. Continue construindo!