Next: Bibliografia
Up: No Title
Previous: No Title
- 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.
Newton Jose Vieira
Fri Feb 18 16:04:52 EDT 2000