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