Autômatos, Linguagens e Computação
Undergraduate Program, Pontifícia Universidade Católica de Campinas, Engenharia de Computação, 2025
Esta disciplina oferece uma imersão nos fundamentos teóricos da computação, explorando a relação intrínseca entre autômatos, linguagens formais e a própria natureza da computabilidade. O estudo desta área é crucial para o desenvolvimento de algoritmos eficientes, a compreensão dos limites da computação e a construção de modelos abstratos que representam sistemas computacionais complexos.
O que vamos trabalhar nesta disciplina?
Nesta disciplina, investigaremos os pilares da Teoria da Computação, abrangendo desde a definição formal de linguagens até a análise dos limites do que pode ser computado. Os principais tópicos abordados incluem:
- Linguagens Formais: Introdução aos conceitos básicos de alfabetos, strings e linguagens, com ênfase na notação e manipulação formal.
- Hierarquia de Chomsky: Estudo detalhado das classes de gramáticas e suas correspondentes linguagens formais, compreendendo as relações entre elas e suas limitações.
- Autômatos de Estados Finitos (AFE): Análise da estrutura e funcionamento dos AFE, incluindo sua aplicação na modelagem de sistemas finitos e no reconhecimento de padrões.
- Máquinas de Turing: Introdução ao modelo teórico de computação mais poderoso conhecido, explorando suas capacidades e limitações para a resolução de problemas computacionais.
- Decidibilidade e Computabilidade: Investigação dos conceitos de decidibilidade e computabilidade, incluindo a demonstração da existência de problemas indecidíveis e não computáveis.
O que esperar?
Esta disciplina é fundamentalmente teórica, exigindo um alto nível de abstração e rigor lógico. Espera-se que os alunos desenvolvam:
- Habilidade de raciocínio formal: Capacidade de analisar e construir argumentos lógicos precisos.
- Compreensão profunda dos conceitos fundamentais da computação: Domínio das bases teóricas que sustentam a Computação moderna.
- Pensamento crítico sobre os limites da computação: Consciência das restrições inerentes aos sistemas computacionais e da impossibilidade de resolver certos problemas.
Bibliografia
- ROSA, J. L. G. Linguagens Formais e Autômatos, 1ª Edição, Editora LTC, 2010. MENEZES, P. B. Linguagens Formais e Autômatos. Série Livros Didáticos, Número 3, 4ª Edição, Editora Sagra Luzzatto, 2002.
- HOPCROFT, J. E.; ULLMAN, J. D.; MOTWANI, Rajeev. Introdução à Teoria de Autômatos, Linguagens e Computação. Tradução da Segunda Edição Americana. Editora Campus, 2003.
- VOSSEN, Gottfried; WITT, Kurt-Ulrich. Grundkurs Theoretische Informatik. Springer Fachmedien Wiesbaden, 2016.