Ementa:
Propriedades e operações com linguagens. Expressões regulares e gramáticas. Modelos de reconhecedores: autômatos finitos, autômatos a pilha, autômatos linearmente limitados, máquinas de Turing. Teorema de Kleene, equivalência entre autômatos a pilha e gramáticas. Hierarquia de Chomsky: linguagens regulares, livre de contexto, sensíveis ao contexto e recursivas. Propriedades de linguagens e funções recursivas. Tese de Church. Problemas indecidíveis: problema da parada, problema da correspondência de Post, redução entre problemas. Classes de problemas: P, NP, NP-Completo.
Periodo:
4
ID Componente Curricular:
06223
Carga Horaria:
60
Tipo:
OBRIGATÓRIO
Anexo ementa:
