計算理論の基礎 [原著第3版] 1.オートマトンと言語

計算理論の基礎となるオートマトンと言語を、数学的な定義や証明の読み方とともに学ぶ教科書である。序論では、オートマトン・計算可能性・計算量の関係、数学用語、定理と証明の基本、証明の型を扱う。続いて、有限オートマトンと非決定性、正規表現、非正規言語を学び、文脈自由文法とプッシュダウン・オートマトン、非文脈自由言語へ進む。決定性文脈自由言語も取り上げる。定理の証明では、証明の考え方や失敗例を示し、問題と解答を収録する。第3版では問題・解答を追加し、第2版以降の研究の進展をいくつかの話題に反映している。