本课程介绍形式语言、自动机、文法、可判定性问题及计算复杂性，内容包括：基础知识；确定性有限自动机、非确定性有限自动机；正则表示与语言；正则语言与正则文法；正则语言的性质、Pumping引理及应用；上下文无关文法与语言；下推自动机、确定性下推自动机；上下文无关语言的性质、上下文无关语言的Pumping 引理及应用；图灵机；不可判定问题、NP问题等。