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