計算理論とオートマトン言語理論[第2版]

初学者でも読み進められるように証明を含め丁寧に記述し，全面的に見直しを行った著者渾身の改訂版．“なるほど，そういうことか”を繰り返し体験して楽しみながら学ぶことができる．章末問題にはすべて解答をつけた． 第I部：計算理論とは／すべては計算から始まる／計算理論のための概念や用語／第II部：有限オートマトン，プッシュダウンオートマトン，そして文脈自由文法／有限オートマトン／文脈自由文法／プッシュダウンオートマトン／第III部：計算可能性／チューリング機械／チューリング機械の万能性とその限界／第IV部：計算の複雑さ／クラスPとクラスNP／論理回路に基づいた計算時間限定の計算／NP完全性