top-right

Autômatos, Linguagens e Computação

Organização e Visão Geral

Pontifícia Universidade Católica de Campinas

Prof. Dr. Denis M. L. Martins

center

Fonte da Imagem: Internet Archive. Veja também: Map of Computer Science YouTube

O que você espera desta disciplina?

Objetivo da Disciplina

Fornecer uma base teórica sólida sobre os fundamentos da computação, explorando a natureza formal de linguagens, a capacidade de máquinas abstratas e os limites intrínsecos do que pode ser computado.

Avaliação

Data Prova Conteúdo
23/09/2025 P1 Autômatos e Linguagens
25/11/2025 P2 Máquinas de Turing e Computabilidade
02/12/2025 Sub Todo o conteúdo da disciplina

Prova Sub (Recuperação): Substitui a nota da atividade de menor conceito.

Atividades Práticas: Valem ponto extra nas provas P1 e/ou P2.

Média Final: Média aritmética das notas obtidas.

Por Que Estudar Teoria da Computação?

  • Fundamento essencial para: Compiladores, Linguagens de Programação, Inteligência Artificial, Verificação Formal.
  • Desenvolvimento do Pensamento Abstrato: Aprender a pensar como um computador – e a entender suas limitações.
  • Compreensão dos Limites da Computação: Descobrir que existem problemas intrínsecamente insolúveis, não importa o quão poderoso seja nosso hardware.
  • Base para Inovação: A Teoria da Computação impulsiona avanços em diversas áreas da ciência e tecnologia – desde a criptografia até a robótica.

Contexto da Disciplina

Trabalhabilidade > Empregabilidade

"In the next five years, 170 million jobs are projected to be created and 92 million jobs to be displaced (...)." - The Future of Jobs - Report 2025, WEF.

Como se preparar para posições de trabalho que ainda não existem?

Contexto da Disciplina (cont.)

"Hiring new people with skills to design AI tools and enhancements appropriate for the organization-specific skills" - The Future of Jobs - Report 2025, WEF.

Ementa e Escopo

  • 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.
  • 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.
  • Decidibilidade e Computabilidade: Investigação dos conceitos de decidibilidade e computabilidade.

O que esperar?

Esta disciplina é fundamentalmente teórica.

  • Habilidade de raciocínio formal.
  • Compreensão profunda dos conceitos fundamentais da computação.
  • Pensamento crítico sobre os limites da computação.

Bibliografia Básica

center

HOPCROFT, J. E.; ULLMAN, J. D.; MOTWANI, Rajeev. Introdução à Teoria de Autômatos, Linguagens e Computação. Editora Campus, 2003.

  • Um clássico! É o livro-texto nesta disciplina.
  • Recomendo leitura atenta e resolução dos exercícios propostos.

Bibliografia Complementar

  • 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.
  • VOSSEN, Gottfried; WITT, Kurt-Ulrich. Grundkurs Theoretische Informatik. Springer Fachmedien Wiesbaden, 2016.

Desde que inventamos as máquinas, sonhamos com a perfeição: automação completa, precisão absoluta...

Mas o que realmente podemos automatizar? E quais são os limites?

Raízes Culturais

  • Talos: autômato da mitologia grega, criado por Hephaestus.
  • Criatura artificial (robô gigante feito de bronze)
  • Programado para realizar proteger a ilha de Creta.
  • Tarefa Complexa: Rondava a ilha três vezes ao dia lançando pedras contra as naus que se aproximavam, impedindo-as de aportar.

Raízes Culturais (cont.)

  • Orloj, Relógio Astronômico de Praga, de 1410
  • Caminhada dos Apóstolos: um show mecânico representado a cada troca de hora com as figuras dos apóstolos e outras esculturas com movimento
  • Programado para exibir o show a cada hora.

Limites da Computação

  • 10° Problema: Dado um polinômio P(x₁, x₂, …, xₙ) com coeficientes inteiros, encontrar um procedimento o qual determina se existe uma solução em números inteiros para a equação P(x₁, x₂, …, xₙ) = 0, usando um número de passos finitos.
  • Em 1970, Yuri Matiyasevich, baseado no trabalho de Martin Davis, Hilary Putnam e Julia Robinson, provou que não existe uma Máquina de Turing que possa decidir, para qualquer polinômio dado, se ele possui uma solução inteira.
  • O 10° problema de Hilbert é indecidível, ou seja, não pode ser resolvido por qualquer procedimento algorítmico, marcando um limite fundamental para a computação.

Dúvidas e Discussão