Programa

• Conceitos Básicos de Matemática
  • Conceitos Básicos de Teoria dos Conjuntos
  • Relações e funções
  • Definições recursivas
  • Conceitos básicos de grafos
  • Indução matemática
• Linguagens Formais
  • Linguagens regulares
    • expressões regulares
    • gramáticas regulares
    • autômatos finitos
    • propriedades
  • Linguagens livres do contexto
    • gramáticas livres do contexto
    • autômatos a pilha
    • propriedades
  • Linguagens sensíveis ao contexto
    • gramáticas sensíveis ao contexto
    • autômatos lineares limitados
    • propriedades
  • Linguagens recursivamente enumeráveis
    • gramáticas irrestritas
    • máquinas de Turing
    • linguagens recursivas
    • propriedades

• Decidibilidade
  • problemas de decisão
  • tese de Church-Turing
  • o problema da parada
  • máquina de Turing universal
  • redutibilidade
  • exemplos de problemas indecidíveis