描述
有限自动机与正则表达式、正则集合的性质、上下文无关文法、下推自动机、确定性上下文无关语言。图灵机、乔姆斯基层次。不可判定性、难解问题。
先修课程
- 先决条件：MATH 3106 或 MATH 3158 或 MATH 3855，或经学院许可。
条件与方式
- 亦列为 COMP 4805。
- 先决条件：MATH 3106 或 MATH 3158 或 MATH 3855，或经学院许可。
- 也以研究生课程提供、要求不同，编号为 MATH 5605，已取得 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/