形式言語とオートマトン

授業目的
言語とそれを生成・受理する「機械」の数学として，文と呼ばれる記号列を生成する規則（文法）の構造と，その文法で生成された記号列の集合である言語を識別する数学的機械である「オートマトン」の構造とを理解し，それらの間にある対応関係であるChomskyの階層について，さらには，チューリングマシンの停止問題を中心とする計算不可能性について学ぶ．
到達目標
形式言語を生成する文法と，その族である正規文法と文脈自由文法・文脈依存文法・句構造文法の概念を把握する．また，形式言語を受理する「機械」の数学として，有限状態オートマトンと、プッシュダウンオートマトン・線形拘束オートマトン・チューリングマシンについて理解する．さらに，それらの文法と機械の間に，言語の族をとおした対応関係であるChomskyの階層を理解する．チューリングマシンの停止問題については，その証明の構造と問題の主張内容を把握する．
授業計画
第1回数学的準備
【授業外学修】
予習：指定教科書第1章を読んできてください．
復習：指定教科書第1章の演習問題をといてください．
第2回有限状態オートマトンとそれが受理する言語
【授業外学修】
予習：指定教科書第2章2.1節を読んできてください．
復習：指定教科書第2章2.1節の演習問題をといてください．
第3回非決定性有限状態オートマトン
【授業外学修】
予習：指定教科書第2章2.2, 2.3節を読んできてください．
復習：指定教科書第2章2.2, 2.3節の演習問題をといてください．
第4回ε動作を持つ有限状態オートマトンと正規表現
【授業外学修】
予習：指定教科書第2章2.4節を読んできてください．
復習：指定教科書第2章2.4節の演習問題をといてください．
第5回状態最小化とポンプの補題
【授業外学修】
予習：指定教科書第2章2.5, 2.6節を読んできてください．
復習：指定教科書第2章2.5, 2.6節の演習問題をといてください．
第6回形式言語：正規言語と有限状態オートマトン
【授業外学修】
予習：指定教科書第3章を読んできてください．
復習：指定教科書第3章の演習問題をといてください．
第7回決定性プッシュダウンオートマトン
【授業外学修】
予習：指定教科書第4章4.1, 4.2, 4.3節を読んできてください．
復習：指定教科書第4章4.1, 4.2, 4.3節の演習問題をといてください．
第8回文脈自由言語
【授業外学修】
予習：指定教科書第4章4.4, 4.5節を読んできてください．
復習：指定教科書第4章4.4, 4.5節の演習問題をといてください．
第9回文脈自由言語とプッシュダウンオートマトン
【授業外学修】
予習：指定教科書第4章4.7, 4.8節を読んできてください．
復習：指定教科書第4章4.7, 4.8節の演習問題をといてください．
第10回構文解析
【授業外学修】
予習：指定教科書第4章4.6節を読んできてください．
復習：指定教科書第4章4.6節の演習問題をといてください．
第11回チューリングマシンと線形拘束オートマトン・Chomskyの階層
【授業外学修】
予習：指定教科書第5章5.1, 5.2節・6章を読んできてください．
復習：指定教科書第5章5.1, 5.2節・6章の演習問題をといてください．
第12回決定不可能性：チューリングマシンの停止問題
【授業外学修】
予習：指定教科書第7章を読んできてください．
復習：指定教科書第7章の演習問題をといてください．
第13回単語の埋め込み表現：文脈非依存
【授業外学修】
復習：講義内容を復習してください．
第14回単語の埋め込み表現：文脈依存
【授業外学修】
復習：講義内容を復習してください．
【授業外学修】コンピュータ言語に関係する。また、コンパイラの授業については本講義内容は必須である。
＊＊こちらの内容は2024年4月1日を基準としたものです．最新のシラバス情報，詳細は大学提供のシラバス情報照会ページシラバス情報照会ページで確認してください＊＊