説明
有限オートマトンと正規表現、正規集合の性質、文脈自由文法、プッシュダウンオートマトン、決定的文脈自由言語。チューリングマシン、チョムスキー階層。不可判定性、計算困難な問題。
前提条件
- 前提条件: COMP 3805 または MATH 3106 または MATH 3158（または MATH 3100）または 学部の許可。
条件および詳細
- MATH 4805 と併載。
- MATH 5605 に対する追加単位は認められない。
- 前提条件: COMP 3805 または MATH 3106 または MATH 3158（または MATH 3100）または 学部の許可。
- 講義週3時間。
原語による参照テキスト
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/