授業科目名 形式言語とオートマトン
履修期 秋 2単位 履修基準年度 2年
授業目的
言語とそれを生成・受理する「機械」の数学として，文と呼ばれる記号列を生成する規則（文法）の構造と，その文法で生成された記号列の集合である言語を識別する数学的機械である「オートマトン」の構造とを理解し，それらの間にある対応関係であるChomskyの階層について，さらには，チューリングマシンの停止問題を中心とする計算不可能性について学ぶ．
到達目標
形式言語を生成する文法と，その族である正規文法と文脈自由文法・文脈依存文法・句構造文法の概念を把握する．また，形式言語を受理する「機械」の数学として，有限状態オートマトンと、プッシュダウンオートマトン・線形拘束オートマトン・チューリングマシンについて理解する．さらに，それらの文法と機械の間に，言語の族をとおした対応関係であるChomskyの階層を理解する．チューリングマシンの停止問題については，その証明の構造と問題の主張内容を把握する．
授業計画
第1回数学的準備
第2回有限状態オートマトンとそれが受理する言語
第3回非決定性有限状態オートマトン
第4回ε動作を持つ有限状態オートマトンと正規表現
第5回状態最小化とポンプの補題
第6回形式言語：正規言語と有限状態オートマトン
第7回決定性プッシュダウンオートマトン
第8回文脈自由言語
第9回文脈自由言語とプッシュダウンオートマトン
第10回構文解析
第11回チューリングマシンと線形拘束オートマトン
第12回言語のクラスとマシンのクラス：Chomskyの階層
第13回決定不可能性：チューリングマシンの停止問題
第14回総合演習