課程說明
有限自動機與正規表示式、正規集合之性質、上下文無關文法、堆疊自動機、確定性上下文無關語言。圖靈機、喬姆斯基階層。不可判定性、難解問題。
先修條件
- 先修科目：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/