Описание
Конечные автоматы и регулярные выражения, свойства регулярных множеств, контекстно-свободные грамматики, магазинные автоматы, детерминированные контекстно-свободные языки. Машины Тьюринга, иерархия Хомского. Неразрешимость, неразрешимые и труднопреодолимые задачи.
Предварительные требования
- Предпосылки: MATH 3106 или MATH 3158 или MATH 3855 или разрешение Школы.
Условия и порядок
- Также перечислено как COMP 4805 .
- Предпосылки: MATH 3106 или MATH 3158 или MATH 3855 или разрешение Школы.
- Также предлагается на уровне магистратуры с другими требованиями как MATH 5605 , за который дополнительный кредит не даётся.
- Лекции три часа в неделю.
Текст источника на языке оригинала
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.
Источники и ссылки
Даты и источники сохраняются, чтобы помочь вам проверить сведения. Переводы предлагаются для удобства чтения; официальным источником для условий и требований является оригинал.
Исходная ссылка : https://calendar.carleton.ca/undergrad/courses/MATH/