计算理论PPT

一.本课的性质以及研究的内容任何一门学科都有它的基础和它的基本问题，如物质的本质是什么？有机体生命的基础和起源是什么？什么是计算机科学的基础？什么是计算机科学的基本问题？诸如什么是形式语言？什么是计算？什么是能计算的？什么是不能计算的？什么是算法？如何评价算法？什么样的算法是可行的？这些问题能否判定？这又引出什么是可判定的？什么是不可判定的？这些问题就是计算理论要讨论的问题。1.1形式语言基本概念（1）1.2文法概念（）1.3文法的分类（）2.1确定的有限自动机（1）2.2不确定的有限自动（）2.3具有ε转移的NFA（）2.4正规表达式及其与有限自动机之间的等价性（1）2.