有限自动机与正则语言；下推自动机和上下文无关语言；图灵机与递归可枚举集；线性有界自动机和上下文敏感语言；可计算性与中止问题；不确定的问题；递归函数；乔姆斯基等级制度；计算复杂性。课程信息：同数学475.3本科学时。3到4个研究生学时。先决条件：CS 373。