Exercícios: Linguagens Regulares e Expressões Regulares 🔍

🎯 Aplicando Teoria na Prática: Desafios Progressivos

Os exercícios desta semana foram cuidadosamente elaborados para consolidar sua compreensão de linguagens regulares e expressões regulares através de aplicações práticas que conectam diretamente com o desenvolvimento do seu Projeto Integrador. Cada exercício aborda aspectos fundamentais que você utilizará na especificação léxica da sua linguagem.

Lembre-se: não existe uma única resposta “correta” para muitos desses problemas. O que importa é seu raciocínio, a clareza das suas justificativas, e como você aplica os conceitos teóricos estudados para resolver desafios práticos.

🔰 Exercício 1: Especificação Léxica para Sistema de Validação

💡 Contexto do Problema

Você foi contratado para desenvolver um sistema de validação de entrada para uma aplicação financeira brasileira. O sistema precisa reconhecer e validar diferentes tipos de dados de entrada dos usuários, garantindo que apenas informações no formato correto sejam aceitas pelo sistema.

Sua tarefa é projetar expressões regulares precisas para reconhecer os seguintes padrões específicos do contexto brasileiro:

Padrão A: Números de CPF no formato XXX.XXX.XXX-XX, onde X representa dígitos de 0 a 9.

Padrão B: Códigos de transação bancária que seguem a estrutura: começam obrigatoriamente com as letras “TB” (maiúsculas), seguidas por exatamente 6 dígitos, depois um hífen, e terminam com exatamente 3 letras maiúsculas.

Padrão C: Valores monetários brasileiros no formato R$ X.XXX.XXX,XX onde:

  • Pode haver de 1 a 3 grupos de três dígitos separados por pontos antes da vírgula
  • Sempre há exatamente dois dígitos após a vírgula
  • O símbolo “R$” é obrigatório no início
  • Deve haver pelo menos um dígito antes da vírgula

🎯 Questões para Resolver

Parte A: Construa expressões regulares formais para cada um dos três padrões descritos. Use notação matemática rigorosa e justifique cada componente da sua expressão.

Parte B: Para o Padrão C (valores monetários), demonstre como sua expressão regular se comporta testando-a com os seguintes exemplos. Indique quais devem ser aceitos e quais devem ser rejeitados, explicando por quê:

  • R$ 1.250,50
  • R$ 999.999.999,99
  • R$ 0,01
  • R$ 123,4
  • $ 1.000,00
  • R$ 1.000.000

Parte C: Analise as limitações das expressões regulares para validação de CPFs reais. Embora sua expressão possa verificar o formato correto, explique por que expressões regulares sozinhas são insuficientes para determinar se um CPF é matematicamente válido.

💭 Reflexões Orientadoras

Este exercício conecta teoria com aplicações práticas que você encontrará constantemente na carreira. Como você balancearia rigidez da validação com usabilidade para usuários? Como trataria variações regionais ou mudanças nos formatos ao longo do tempo?

🎯 Exercício 2: Otimização e Equivalência de Expressões Regulares

🔬 Análise Avançada de Padrões

Durante o desenvolvimento do seu compilador, você descobriu que diferentes membros da equipe criaram expressões regulares distintas para reconhecer o mesmo tipo de token léxico. Agora você precisa determinar se essas expressões são equivalentes e qual versão é mais eficiente para implementação.

Considere as seguintes expressões regulares que supostamente reconhecem o mesmo conjunto de strings:

Expressão Alpha: (a|b)^*a(a|b)^*

Expressão Beta: (a|b)^*a((a|b)(a|b))^*

Expressão Gamma: ((a|b)(a|b))^*a(a|b)^*|a(a|b)^*

Expressão Delta: (b^*ab^*)^+(b^*ab^*|a)^*

🎯 Questões para Resolver

Parte A: Determine formalmente quais dessas expressões são equivalentes (reconhecem exatamente o mesmo conjunto de strings). Para cada par de expressões que você considera equivalentes, forneça uma prova baseada nas propriedades algébricas das expressões regulares. Para pares não equivalentes, forneça contra-exemplos específicos que mostram a diferença.

Parte B: Para cada expressão, caracterize formalmente a linguagem que ela reconhece. Descreva em português claro e preciso quais strings pertencem à linguagem de cada expressão, identificando os padrões subjacentes.

Parte C: Assumindo que você precise implementar essas expressões como parte de um analisador léxico de alta performance, analise qual versão seria mais eficiente. Considere fatores como:

  • Número de estados no autômato finito resultante
  • Complexidade de construção
  • Facilidade de manutenção e modificação
  • Legibilidade para outros desenvolvedores

💡 Orientações para Desenvolvimento

Este exercício desenvolve habilidades essenciais para otimização de compiladores. Na prática, escolhas aparentemente pequenas na especificação léxica podem ter impacto significativo na performance final do compilador. Como você abordaria o trade-off entre elegância matemática e eficiência prática?

🚀 Exercício 3: Projeto de Linguagem Regular Customizada

🎨 Desafio de Design Avançado

Como desafio culminante desta semana, você criará uma especificação léxica completa para um domínio específico que requer precisão extrema: um sistema de controle de tráfego aéreo que processa comandos de voo em linguagem natural controlada.

Este sistema deve reconhecer comandos de navegação aérea que seguem padrões internacionais rígidos, mas com flexibilidade suficiente para permitir variações operacionais necessárias na aviação real.

🛩️ Especificações do Sistema

Seu analisador léxico deve reconhecer exatamente os seguintes tipos de tokens:

Indicativos de Aeronave: Começam com 2-3 letras maiúsculas (código da companhia), seguidas por 1-4 dígitos (número do voo). Exemplos: TAM3054, GOL1234, AA1, VRG987

Altitudes: Começam obrigatoriamente com “FL” (Flight Level) seguido por exatamente 3 dígitos, OU começam com “ALT” seguido por 1-5 dígitos. Exemplos: FL350, FL045, ALT12000, ALT500

Direções de Proa: Começam com “HDG” seguido por exatamente 3 dígitos (000-359), OU começam com “TURN” seguido por “LEFT” ou “RIGHT”, depois um espaço, depois 1-3 dígitos. Exemplos: HDG270, TURNLEFT45, TURNRIGHT120

Velocidades: Começam com “SPD” seguido por 2-3 dígitos, OU formato “M” (Mach) seguido por “0.” e exatamente 2 dígitos. Exemplos: SPD250, SPD85, M0.84, M0.92

🎯 Questões para Resolver

Parte A: Projete expressões regulares formais e precisas para cada tipo de token descrito. Sua especificação deve ser rigorosa o suficiente para evitar ambiguidades, mas flexível o suficiente para capturar todas as variações válidas.

Parte B: Identifique e resolva potenciais conflitos entre suas expressões regulares. Se múltiplas expressões podem reconhecer a mesma string, proponha uma estratégia de resolução baseada em prioridades operacionais da aviação.

Parte C: Teste rigorosamente suas expressões com os seguintes casos de entrada complexos. Para cada caso, determine quais tokens devem ser reconhecidos e quais devem ser rejeitados, explicando seu raciocínio:

TAM3054 FL350 HDG090 SPD280
GOL1 ALT5000 TURNRIGHT15 M0.78
XXX9999 FL999 HDG360 SPD99999
AB FL12 TURNLEFT M1.50
VRG123ABC ALT-500 HDG045A SPD250KT

Parte D: Analise as limitações fundamentais das linguagens regulares para este domínio. Que aspectos da validação de comandos aéreos não podem ser capturados por expressões regulares sozinhas? Como essas limitações afetariam o design de um sistema real?

🔍 Considerações Avançadas

Este exercício simula desafios reais de especificação de linguagens onde precisão é literalmente questão de segurança. Como você balancearia completude da especificação com simplicidade de implementação? Que estratégias usaria para manter a especificação atualizada conforme padrões internacionais evoluem?

Considere também como este tipo de análise se aplica ao seu Projeto Integrador. Que paralelos você identifica entre especificação de tokens aéreos e especificação léxica da linguagem que seu grupo está desenvolvendo?

🌟 Reflexões sobre o Processo de Aprendizagem

💭 Conectando Exercícios com Conceitos Fundamentais

Estes exercícios foram projetados para consolidar sua compreensão de linguagens regulares e expressões regulares de forma que prepare você para desafios reais em design de compiladores. Cada problema envolveu múltiplos conceitos trabalhando juntos: especificação formal de padrões, análise de equivalência, otimização para implementação prática, e resolução de conflitos entre especificações.

À medida que você trabalha através destes problemas, observe como precisão matemática não é obstáculo, mas ferramenta poderosa que torna possível especificar comportamentos complexos de forma inequívoca. Esta precisão será absolutamente essencial quando você começar a implementar o analisador léxico do seu compilador.

🚀 Preparação para Aplicações Futuras

As habilidades que você desenvolve resolvendo estes exercícios se traduzem diretamente em competências que usará ao longo do curso:

Especificação de Tokens do Exercício 1 prepara você para definir formalmente todos os elementos léxicos da sua linguagem de programação. As técnicas que você usou aqui aparecerão quando especificar identificadores, literais, operadores, e palavras-chave da sua linguagem.

Análise de Equivalência do Exercício 2 estabelece fundação para otimizar especificações léxicas em termos de performance e manutenibilidade. Propriedades de equivalência que você explorou aqui determinarão quais transformações são válidas durante otimização de compiladores.

Design Sistemático do Exercício 3 prepara você para enfrentar problemas de especificação em domínios complexos e com restrições rigorosas. A abordagem metodológica que você desenvolveu aqui será essencial quando seu grupo enfrentar decisões arquiteturais no Projeto Integrador.

🎯 Próximos Passos em Sua Jornada

Depois de trabalhar através destes exercícios, você deve sentir confiança crescente em sua capacidade de aplicar teoria de linguagens regulares para resolver problemas práticos complexos. Esta confiança será fundamental quando você começar a estudar autômatos finitos determinísticos na próxima semana.

Lembre-se de que domínio verdadeiro vem através da prática repetida e aplicação em contextos variados. Continue procurando oportunidades para aplicar expressões regulares em projetos de programação que você desenvolve, em problemas de processamento de texto que você encontra, e em discussões técnicas sobre especificação de linguagens.

🔮 Antecipando o Próximo Tema

Na próxima semana, você descobrirá como as expressões regulares que dominou se materializam em algoritmos concretos através dos autômatos finitos determinísticos. Você verá como especificações algébricas elegantes se transformam em máquinas de estados eficientes que podem ser implementadas diretamente em software.

As questões que você deve ter em mente são: Como um computador realmente “executa” uma expressão regular? Que estruturas de dados e algoritmos tornam possível o reconhecimento eficiente de padrões? Como as limitações das linguagens regulares se manifestam na prática?

Estas questões guiarão nossa exploração na próxima semana, quando você descobrirá a conexão profunda entre álgebra abstrata e engenharia de software prática.