言語と計算

計算とは何か？　コンピューターの動作はもちろん計算といえる。また、人間が話したり、考えたりすることも計算の一つの形である。このように計算という概念を幅広く捉え、様々な種類に分けて解説する。そして最終的には、計算機の数学的モデルといわれるチューリング機械がどのような構造を持っているかを理解する。文法によって生成される（形式）言語がどのようなものかを理解する際、文法によって生成される言語と、オートマトン（言語を計算するための機械）によって計算される言語の関連性を理解することも目標となる。

１．準備
２．言語
３．チョムスキーの階層
４．有限オートマトン
５．オートマトンによって受理される言語
６．非決定性オートマトン
７．決定性オートマトンと非決定性オートマトン
８．正規文法とオートマトン
９．２方向有限オートマトン
１０．１方向オートマトンと２方向オートマトン
１１．ε―動作を含む非決定性オートマトン
１２．正規表現
１３．チューリング機械
１４．さまざまなチューリング機械
１５．アルゴリズムの概念