描述
有限自动机与正则表达式、正则集合的性质、上下文无关文法、下推自动机、确定性上下文无关语言。图灵机、乔姆斯基层次。不可判定性、难解问题。
先修课程
- 先修课：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/