Descrição
Autómatos finitos e expressões regulares, propriedades de conjuntos regulares, gramáticas livres de contexto, autómatos de pilha, linguagens determinísticas livres de contexto. Máquinas de Turing, hierarquia de Chomsky. Indecidibilidade, problemas intratáveis.
Pré-requisitos
- Pré-requisito(s): COMP 3805 ou MATH 3106 ou MATH 3158 (ou MATH 3100) ou permissão da School.
Condições e modalidades
- Também listado como MATH 4805.
- Impede crédito adicional por Impede crédito adicional por MATH 5605.
- Pré-requisito(s): COMP 3805 ou MATH 3106 ou MATH 3158 (ou MATH 3100) ou permissão da School.
- Aulas três horas por semana.
Texto de referência na sua língua de origem
Finite automata and regular expressions, properties of regular sets, context-free grammars, pushdown automata, deterministic context-free languages. Turing machines, the Chomsky hierarchy. Undecidability, intractable problems.
- Prerequisite(s): COMP 3805 or MATH 3106 or MATH 3158 (or MATH 3100) or permission of the School.
- Also listed as MATH 4805 .
- Precludes additional credit for Precludes additional credit for MATH 5605 .
- Lectures three hours a week.
Fontes e referências
As datas e as fontes são mantidas para ajudá-lo a verificar os dados. As traduções são propostas para facilitar a leitura; a fonte oficial é a referência para condições e exigências.
Fonte de referência : https://calendar.carleton.ca/undergrad/courses/COMP/