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): MATH 3106 ou MATH 3158 ou MATH 3855 ou permissão da Escola.
Condições e modalidades
- Também listado como COMP 4805 .
- Pré-requisito(s): MATH 3106 ou MATH 3158 ou MATH 3855 ou permissão da Escola.
- Também oferecida em nível de pós-graduação, com requisitos diferentes, como MATH 5605 , para a qual crédito adicional é impedido.
- 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): MATH 3106 or MATH 3158 or MATH 3855 or permission of the School.
- Also listed as COMP 4805 .
- Also offered at the graduate level, with different requirements, as MATH 5605 , for which additional credit is precluded.
- 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/MATH/