可計算性和複雜性

目錄

本書旨在作為可計算性理論和複雜性理論的入門教科書，重點介紹形式語言。目標讀者是具有程式設計、資料結構和離散數學背景的計算機科學和數學學生，例如計算機科學專業的二年級學生。

• 介紹
• 形式語言
  • 喬姆斯基層次
    • 正則語言 - 示例 DFA 輸入
    • 上下文無關語言 - 示例 PDA 輸入
    • 上下文敏感語言 - 示例 LBA 輸入
    • 無限制語言 - 示例 TM 輸入
  • 其他語言類別
    • 計數語言 - 示例 CA 輸入
• 可計算性
  • 可判定性
  • 可歸約性
• 複雜性
  • 時間複雜性
    • P
    • P-完全
    • NP
    • NP-完全
  • 空間複雜性
    • L
    • NL
    • NL-完全
    • PSPACE
    • PSPACE-Complete
• 參考文獻和進一步閱讀