学部後期課程
HOME 学部後期課程 形式言語理論
過去(2017年度)の授業の情報です
学内のオンライン授業の情報漏洩防止のため,URLやアカウント、教室の記載は削除しております。
最終更新日:2024年3月15日

授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。

形式言語理論

正則言語、文脈自由言語、及びオートマトンについての基本的な概念と定理を理解する。
正則言語については、有限オートマトンと正則表現の関係、正則言語の性質、状態数最小有限オートマトン、順序機械、関連するアルゴリズム、および形式検証への応用可能性について学ぶ。
文脈自由文法とそれに関連する概念について学ぶ。そして、文脈自由言語の性質、Pumping Lemma (uvwxy定理)、Ogdenの定理、プッシュダウン・オートマトン、及び関連するアルゴリズムについて理解する。
MIMA Search
時間割/共通科目コード
コース名
教員
学期
時限
0510002
FSC-IS2002L1
形式言語理論
蓮尾 一郎
A1 A2
金曜4限
マイリストに追加
マイリストから削除
講義使用言語
日本語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
開講所属
理学部
授業計画
1.基本的定義と記法 1.1 関係と部分関数 1.2 記号列,アルファベット,言語 2 有限オートマトンと正則言語 2.1 有限オートマトン序章:「ある離れ小島で」 2.2 有限オートマトンの定義 2.3 非決定性有限オートマトンと決定性有限オートマトンの等価性 2.4 ε動作付非決定性有限オートマトン 2.5 正則言語のPumping Lemma 2.6 正則表現 2.7 有限オートマトンと正則表現 2.8 正則言語の性質 2.9 ブール行列による有限オートマトンの表現 2.10 最小オートマトン 2.10.1 Myhill-Nerode の定理 2.10.2 状態数の最小化 2.11 順序機械 2.12 有限オートマトンについてのアルゴリズム 3.文脈自由文法 3.1 定義と例 3.1.1 導出木 3.2 文法の簡素化 3.2.1 無駄な変数の除去 3.2.2 A → εの形の生成規則 3.2.3 A → B の形の生成規則 3.3 Chomsky 標準形 3.4 文脈自由言語の性質 3.4.1 Pumping Lemma 3.4.2 Ogdenの定理 3.5 文脈自由文法の所属性判定問題 3.6 有限オートマトンと正則文法 4.Turing 機械 4.1 定義 4.2 Turing 機械による関数の計算 4.3 Turing 機械の変種 4.3.1 非決定性Turing 機械 4.3.2 マルチテープTuring 機械 4.3.3 両方向に無限の長さをもつテープ 4.3.4 オフラインTuring 機械 4.3.5 多次元テープTuring 機械 4.3.6 その他の計算のモデル 4.4 Church のテーゼ 4.5 帰納的可算集合と帰納的集合 4.6 決定不能な問題
授業の方法
講義資料(配布)に基づいた板書.
成績評価方法
期末試験による.レポート(ほぼ毎回,出席確認を兼ねる)も加味する.
教科書
講義のなかで配布する.
参考書
●John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, (2nd Edition), Addison-Wesley Pub Co, 2000; ISBN: 0201441241. ●M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Publishing Company, 1978. ●有川節夫,宮野悟,「オートマトンと計算可能性」(第1章,2章,3章),培風館,1986. ●宮野悟,「並列アルゴリズム」(第1章),近代科学社,1994.
その他
講義開始は 2017/9/29 (金)を予定. ウェブページ http://group-mmm.org/~ichiro/COURSE_formalLang2017.html その他で最新情報を通知する.