可计算性和复杂性

目录

本书旨在作为可计算性理论和复杂性理论的入门教科书，重点介绍形式语言。目标读者是具有编程、数据结构和离散数学背景的计算机科学和数学学生，例如计算机科学专业的二年级学生。

• 介绍
• 形式语言
  • 乔姆斯基层次
    • 正则语言 - 示例 DFA 输入
    • 上下文无关语言 - 示例 PDA 输入
    • 上下文敏感语言 - 示例 LBA 输入
    • 无限制语言 - 示例 TM 输入
  • 其他语言类别
    • 计数语言 - 示例 CA 输入
• 可计算性
  • 可判定性
  • 可归约性
• 复杂性
  • 时间复杂性
    • P
    • P-完全
    • NP
    • NP-完全
  • 空间复杂性
    • L
    • NL
    • NL-完全
    • PSPACE
    • PSPACE-Complete
• 参考文献和进一步阅读