シラバス参照

授業情報／Course information

科目一覧へ戻る 2020/10/22 現在

授業基本情報
科目名（和文）
／Course		 形式言語理論
科目名（英文）
／Course
時間割コード
／Registration Code		 61110501
学部（研究科）
／Faculty		 情報系工学研究科 博士前期課程
学科（専攻）
／Department		 システム工学専攻
担当教員（○：代表教員）
／Principle Instructor （○） and Instructors		 ○國島　丈生
オフィスアワー
／Office Hour		 國島　丈生(前期：金曜4限、後期：金曜4限、いずれも2610室)
開講年度
／Year of the Course		 2020年度
開講期間
／Term		 前期
対象学生
／Eligible Students		 1年,2年
単位数
／Credits		 2.0
授業概要情報
更新日
／Date of renewal		 2020/02/28
使用言語
／Language of Instruction		 日本語
オムニバス
／Omnibus		 該当なし
授業概略と目的
／Cource Description and Objectives		 言語理論とオートマトン理論のうち、有限オートマトンと正則表現（正規表現）、文脈自由文法、プッシュダウンオートマトンなど、情報科学の理論・応用の両面で重要になっている項目について学び、理解を深めます。
履修に必要な知識・能力・キーワード
／Prerequisites and Keywords		 履修に必要な知識: 集合、数学的帰納法など、情報数学の基本事項
履修上の注意
／Notes		 有限オートマトンはソフトウェア、通信プロトコル、論理設計など、情報科学の多くの分野で使われる。また正則表現（正規表現）や文脈自由文法も実際に使われることの多い概念である。講義や予復習を通して、深く理解するように各自努力することが望ましい。
教科書
／Textbook(s)		 「オートマトン 言語理論 計算論I (第2版)」, J. ホップクロフトほか, サイエンス社
参考文献等
／References		 本講義で講述する内容については、多数の教科書が出版されており、Webでも多数の史料が発見できる。本講義で使用する教科書が分かりにくい場合は適宜これらを参照し、理解を深めると良い。
自主学習ガイド
／Expected Study Guide outside Coursework/Self-Directed Learning Other Than Coursework		 講義時間の制約上、証明の詳細は省略することが多いが、言語理論を深く理解するには教科書に掲載されている証明も時間をかけて読んでみることが望ましい。
資格等に関する事項
／Attention Relating to Professional License
備考
／Notes
授業計画詳細情報
No. 単元（授業回数）
／Unit (Lesson Number)		 単元タイトルと概要
／Unit Title and Unit Description		 時間外学習
／Preparation and Review		 配付資料
／Handouts
1 1 [導入]
本講義で扱う内容について、応用面も含めて俯瞰的な説明を行う。		 教科書1.1〜1.4節の理解
2 2 [言語理論の基礎概念]
本講義を通して用いる言語理論の基礎的な概念について説明する。		 教科書1.5節の理解
3 3 [決定性有限オートマトン(DFA)]
DFAの概要、定義、動作などについて、例を用いながら説明する。		 教科書2.2節の理解
4 4 [非決定性有限オートマトン(NFA)]
NFAの定義や動作についてDFAと対比させながら説明し、DFAとNFAの等価性を示す。		 教科書2.3節の理解
5 5 [ε動作付き非決定性有限オートマトン(ε-NFA)]
ε-NFAの定義や動作、DFAとε-NFAの等価性などについて講述する。		 教科書2.4〜2.5節の理解
6 6 [正則表現]
正則表現（正規表現）について、言語理論の視点から説明する。		 教科書3.1節の理解
7 7 [正則表現と有限オートマトンの等価性]
正則表現と有限オートマトンの等価性について、証明の概要を交えて説明する。		 教科書3.2節の理解
8 8 [正則言語とその性質]
ポンプの補題、正則言語の閉包性などについて説明する。		 教科書4.1〜4.2節の理解
9 9 [有限オートマトンの状態数最小化]
有限オートマトンの状態数最小化アルゴリズムについて説明する。		 教科書4.4節の理解
10 10 [文脈自由文法(CFG)]
CFGの定義や意味について、例を用いながら説明する。		 教科書5.1節の理解
11 11 [構文木とCFG]
文脈自由文法と関わりの深いデータ構造である構文木について、CFGとの関連を交えて説明する。		 教科書5.2節の理解
12 12 [文脈自由文法の応用]
CFGが実際にどのように活用されているのか、例を交えて説明する。		 教科書5.3〜5.4節の理解
13 13 [プッシュダウンオートマトン(PDA)]
PDAの概要、定義、動作などについて説明する。		 教科書6.1〜6.2節の理解
14 14 [CFGとPDAの等価性]
CFGとPDAの等価性について、証明の概要を交えて説明する。		 教科書6.3節の理解
15 15 [文脈自由言語とその性質]
CFGに関する諸性質について説明する。		 教科書7.1〜7.3節の理解
授業評価詳細情報
到達目標及び観点／Learning Goal and Specific Behavioral Viewpoints
No. 到達目標
／Learning Goal		 知識・理解
／Knowledge & Undestanding		 技能・表現
／Skills & Expressions		 思考・判断
／Thoughts & Decisions		 伝達・コミュニケーション
／Communication		 協働
／Cooperative Attitude
1 有限オートマトンの主要な性質、応用の理解 ○ ○
2 正則表現の主要な性質、応用の理解 ○ ○
3 文脈自由文法とプッシュダウンオートマトンの主要な性質、応用の理解 ○ ○
成績評価方法と基準／Evaluation of Achievement
※出席は2/3以上で評価対象となります。
No. 到達目標
／Learning Goal		 定期試験
／Exam.		 レポート課題
1 有限オートマトンの主要な性質、応用の理解 ○
2 正則表現の主要な性質、応用の理解 ○
3 文脈自由文法とプッシュダウンオートマトンの主要な性質、応用の理解 ○
評価割合（％）
／Allocation of Marks		 100

科目一覧へ戻る