01 / 経典教科書推薦
経典教科書推薦
対象読者
多くはコンピュータサイエンス学位の2・3年次に、計算理論や形式言語の最初の科目を履修する学部生に向く。中心となる考え方を定義や定理の前に動機づけの例で導入するため、簡潔で形式的な記述に苦労する学生を主な読者として想定している。
前提知識
集合、関数、関係、グラフ、数学的帰納法による証明を含む離散数学と、ある程度のプログラミング経験。
扱う内容
数学的準備、決定性・非決定性有限オートマトン、正規言語・正規表現・正規文法、正規言語の性質とポンピング補題、文脈自由言語と文法、その簡約と標準形、プッシュダウンオートマトン、文脈自由言語の性質、チューリング機械とチューリングの提唱、その他の計算モデル、帰納的可算言語とチョムスキー階層、アルゴリズム的計算の限界、計算複雑性入門、そしてこの版で新たに加わった構文解析への応用を扱う。
使い方
各節を動機づけの例とともに読み、難しい問題の前に導入的な演習に取り組む。オートマトンを描き、例となる入力に対する動作を手やシミュレータでたどる。構文解析の章はコンパイラの授業と並行して読むと、理論の応用が見えてくる。
版と出典
第7版。Jones & Bartlett Learning より2022年刊、著作権表示は2023年（ISBN 9781284231601）。構文解析に関する3章が追加された。本レコードの書誌データは Jones & Bartlett Learning の商品ページに基づき、Google Books で照合した。