Programa

1

Conceitos Básicos de Matemática: representação; prova de teoremas; conjuntos; relações; funções; conjuntos enumeráveis; definições recursivas; indução matemática; grafos; linguagens formais; gramáticas; problemas de decisão.

2

Linguagens Formais

0.1

Linguagens regulares: expressões regulares; gramáticas regulares; autômatos finitos; propriedades.

0.2

Linguagens livres do contexto: gramáticas livres do contexto; autômatos de pilha; propriedades.

0.3

Linguagens sensíveis ao contexto: gramáticas sensíveis ao contexto; autômatos lineares limitados; propriedades.

0.4

Linguagens recursivamente enumeráveis: gramáticas irrestritas; máquinas de Turing; linguagens recursivas; propriedades.

3

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