放送大学教材
計算論〔改訂版〕
改訂版
著：隈部正博
紙版
内容紹介
計算とは何か？ コンピュータの動作はもちろん計算といえる。また人間の話す言語やその文法も計算の１つの形である。このように計算という概念を幅広く捉え、様々な種類に分けて解説する。そして最終的には、計算機の数学的モデルといわれるチューリング機械がどのような構造を持っているかを理解する。また文法によって生成される（形式）言語がどのようなものか理解し、様々な文法と言語との関わりを理解する。その際、文法によって生成される言語と、オートマトンによって計算される言語の関連性を理解することが目標となる。
目次
1.準備(A) 2.言語 3.チョムスキーの階層 4.有限オートマトン 5.オートマトンによって受理される言語 6.非決定性オートマトン 7.決定性オートマトンと非決定性オートマトン 8.正規文法とオートマトン 9.2方向有限オートマトン 10.1方向オートマトンと2方向オートマトン 11.ε－動作を含む非決定性オートマトン 12.正規表現 13.チューリング機械 14.様々なチューリング機械 15.アルゴリズムの概念
