语言与机器: 计算机科学理论导论

封面\n书名\n版权\n前言\n目录\n第一部分　基础\n第1章  数学预备知识\n1.1　集合论\n1.2　笛卡儿积、关系和函数\n1.3　等价关系\n1.4　可数集合和不可数集合\n1.5　对角化和自反\n1.6　递归定义\n1.7　数学归纳\n1.8　有向图\n1.9　练习\n参考文献注释\n第2章  语言\n2.1　字符串和语言\n2.2　语言的有穷规格说明\n2.3　正则集合和表达式\n2.4　正则表达式和文本搜索\n2.5　练习\n参考文献注释\n第二部分　文法、自动机和语言第3章  上下文无关文法\n3.1　上下文无关文法和语言\n3.2　文法和语言的例子\n3.3　正则文法\n3.4　验证文法\n3.5　最左推导和二义性\n3.6　上下文无关文法和编程语言定义\n3.7　练习\n参考文献注释\n第4章  上下文无关文法范式\n4.1　文法转换\n4.2　消去λ规则\n4.3　去掉链规则\n4.4　无用符\n4.5　乔姆斯基范式\n4.6　CYK算法\n4.7　去掉直接左递归\n4.8　格立巴赫范式\n4.9　练习\n参考文献注释\n第5章  有限自动机\n5.1　一个有限状态自动机\n5.2　确定型有限自动机\n5.3　状态图和例子\n5.4　非确定型有限自动机\n5.5　λ-转换\n5.6　去掉非确定性\n5.7　DFA的最小化\n5.8　练习\n参考文献注释\n第6章  正则语言的性质\n6.1　有限状态机接收正则语言\n6.2　表达式图\n6.3　正则文法和有限自动机\n6.4　正则语言的封闭性质\n6.5　非正则语言\n6.6　规则语言的泵引理\n6.7　Myhill-Nerode定理\n6.8　练习\n参考文献注释\n第7章  下推自动机和上下文无关语言\n7.1　下推自动机\n7.2　PDA的变种\n7.3　上下文无关语言的接收\n7.4　上下文无关语言的泵引理\n7.5　上下文无关语言的封闭性\n7.6　练习\n参考文献注释\n第三部分　可计算性第8章  图灵机\n8.1　标准图灵机\n8.2　作为语言接收器的图灵机\n8.3　可供选择接收标准\n8.4　多道图灵机\n8.5　双向图灵机\n8.6　多带图灵机\n8.7　非确定型图灵机\n8.8　用来枚举语言的图灵机\n8.9　练习\n参考文献注释\n第9章  图灵可计算函数\n9.1　函数的计算\n9.2　数值计算\n9.3　图灵机的顺序操作\n9.4　函数的合成\n9.5　不可计算函数\n9.6　关于编程语言\n9.7　练习\n参考文献注释\n第10章  乔姆斯基层次\n10.1　无限制文法\n10.2　上下文有关文法\n10.3　线性有界自动机\n10.4　乔姆斯基层次\n10.5　练习\n参考文献注释\n第11章  判定问题与丘奇—图灵论题\n11.1　判定问题的描述\n11.2　判定问题和递归语言\n11.3　问题归约\n11.4　丘奇—图灵论题\n11.5　通用机\n11.6　练习\n参考文献注释\n第12章  不可判定性\n12.1  图灵机的停机问题\n12.2　问题归约和不可判定性\n12.3　其他的停机问题\n12.4　莱斯定理\n12.5　不可解决的词问题\n12.6　波斯特对应问题\n12.7　上下文无关文法中的不可判定问题\n12.8　练习\n参考文献注释\n第13章　Mu-递归函数\n13.1　原始递归函数\n13.2　一些原始递归函数\n13.3　有界操作符\n13.4　除法函数\n13.5　歌德尔数字和串值递归\n13.6　可计算部分函数\n13.7　图灵可计算函数和Mu-递归函数\n13.8　修订的丘奇—图灵论题\n13.9　练习\n参考文献注释\n第四部分　计算复杂性第14章  时间复杂性\n14.1　复杂性度量\n14.2　增长的速度\n14.3　图灵机的时间复杂性\n14.4　复杂性和图灵机的变种\n14.5　线性加速\n14.6　语言时间复杂性的属性\n14.7　计算机计算的模拟\n14.8　练习\n参考文献注释\n第15章  P、NP和库克定理\n15.1  非确定型图灵机的时间复杂性\n15.2　P类和NP类\n15.3　问题表示和复杂性\n15.4　判定问题和复杂性类\n15.5　哈密尔顿回路问题\n15.6　多项式时间归约\n15.7　P=NP?\n15.8　可满足性问题\n15.9　复杂类的关系\n15.10　练习\n参考文献注释\n第16章  NP-完全问题\n16.1  归约和NP-完全问题\n16.2　三元可满足性问题\n16.3　三元可满足性的归约\n16.4　归约和子问题\n16.5　最优化问题\n16.6　近似算法\n16.7　近似方案\n16.8　练习\n参考文献注释\n第17章  其他复杂性类\n17.1　派生的复杂性类\n17.2　空间复杂性\n17.3　空间复杂性和时间复杂性的关系\n17.4　P-空间，NP-空间和萨维奇定理\n17.5　P-空间完全性\n17.6　一个难解问题\n17.7　练习\n参考文献注释\n第五部分　确定型语法分析第18章　语法分析引论\n18.1　文法图\n18.2　自顶向下语法分析\n18.3　归约和自底向上语法分析\n18.4　自底向上语法分析器\n18.5　语法分析和编译\n18.6　练习\n参考文献注释\n第19章  LL（k）文法\n19.1　上下文无关文法中的预读\n19.2　FIRST集合、FOLLOW集合和预读集合\n19.3　强LL（k）语法\n19.4　FIRSTk集合的构造\n19.5　FOLLOWk集合的构造\n19.6　强LL（1）文法\n19.7　强LL（k）分析器\n19.8　LL（k）文法\n19.9　练习\n参考文献注释\n第20章  LR（k）文法\n20.1　LR（0）上下文\n20.2　LR（0）分析器\n20.3　LR（0）机\n20.4　被LR（0）机接收\n20.5　LR（1）文法\n20.6　练习\n参考文献注释\n附录Ⅰ  标记索引\n附录Ⅱ  希腊字母表\n附录Ⅲ  ASCⅡ字符集\n附录Ⅳ  Java的BNF范式定义\n参考文献\n索引