Programa

• 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.
• 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 e Linguagens Regulares: expressões regulares; gramáticas regulares; linguagens regulares: conclusão.
• Autômatos a Pilha: uma introdução informal; autômatos a pilha determinísticos; autômatos a pilha não determinísticos; gramáticas livres do contexto; linguagens livres do contexto: propriedades.
• Máquinas de Turing: uma introdução informal; máquinas de Turing determinísticas; máquinas de Turing não determinísticas; gramáticas irrestritas; linguagens recursivamente enumeráveis; linguagens recursivas.
• Decidibilidade: a tese de Church-Turing; máquina de Turing universal; o problema da parada; redutibilidade; exemplos de problemas indecidíveis.