Programa

1

Conceitos Preliminares: 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

Máquinas de Estado-Finito: alguns exemplos; autômatos finitos determinísticos; autômatos finitos não determinísticos; linguagens regulares: propriedades; máquinas de Mealy e de Moore; expressões regulares; gramáticas regulares; linguagens regulares: conclusão.

3

Autômatos com Pilha: uma introdução informal; autômatos com pilha determinísticos; autômatos com pilha não determinísticos; gramáticas livres do contexto; linguagens livres do contexto: propriedades.

4

Máquinas de Turing: o que é máquina de Turing; algumas variações de máquinas de Turing; gramáticas e máquinas de Turing; propriedades das linguagens recursivamente enumeráveis e linguagens recursivas.

5

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