授業科目名：

対象学年：

開講学期：

開講形態：

　今日の計算機の基礎的なモデルとなったオートマトンと，それと 双対をなす形式言語理論について学ぶ．
　オートマトンとは計算機の数学的モデルであり，形式言語理論は 自然言語やプログラミング言語の数学的モデルである．これらはそ の“複雑さ”に応じていくつかのクラスに分けられ，かつ両者の間 には強い関係がある．この講義では，オートマトン理論および形式 言語理論を通して，“計算”ということを厳密にかつ数学的に考察 する．
　講義の前半は，最も単純なモデルである有限オートマトンと正規 文法について述べる．後半では，プッシュダウンオートマトンと文 脈自由文法について述べ，これらの計算能力が等価であることを示 す．特に文脈自由文法については詳しく取り扱い，その諸性質につ いて述べる．

第1週　　　　　言語と文法　
第2週　　　　　文法とオートマトンの階層
第3週--第5週　　有限オートマトン（決定性，非決定性有限オートマトン等）　
第6週--第7週　　正規文法　
第8週--第11週　　文脈自由文法とその標準形
第12週--第14週　プッシュダウン・オートマトン
第15週　　　　最近のオートマトン理論　

筆記試験

J.ホップクロフト・J.ウルマン，言語理論とオートマトン，サイエンス社，2,900円

J.ホップクロフト・J.ウルマン，オートマトン・言語理論・計算論I，II， サイエンス社，各2,900円

学習の基礎として，「情報数学I」を履修していること を前提として講義を行う．