  シラバス参照
|
| 科目一覧へ戻る | 2019/08/20 現在 |
| 科目名（和文） ／Course |
形式言語理論 |
|---|---|
| 科目名（英文） ／Course |
Formal Language Theory |
| 時間割コード ／Registration Code |
61110501 |
| 学部（研究科） ／Faculty |
情報系工学研究科 博士前期課程 |
| 学科（専攻） ／Department |
システム工学専攻 |
| 担当教員（○：代表教員）
／Principle Instructor （○） and Instructors |
○國島 丈生 |
| オフィスアワー ／Office Hour |
國島 丈生(月曜5限) |
| 開講年度 ／Year of the Course |
2017年度 |
| 開講期間 ／Term |
前期 |
| 対象学生 ／Eligible Students |
1年,2年 |
| 単位数 ／Credits |
2.0 |
| 更新日 ／Date of renewal |
2017/03/21 |
|---|---|
| 使用言語 ／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節の理解 |
| No. |
到達目標 ／Learning Goal |
知識?理解 ／Knowledge & Undestanding |
技能?表現 ／Skills & Expressions |
思考?判断 ／Thoughts & Decisions |
伝達?コミュニケーション ／Communication |
協働 ／Cooperative Attitude |
||
|---|---|---|---|---|---|---|---|---|
| 1 | 有限オートマトンの主要な性質、応用の理解 | ○ | ○ | |||||
| 2 | 正則表現の主要な性質、応用の理解 | ○ | ○ | |||||
| 3 | 文脈自由文法とプッシュダウンオートマトンの主要な性質、応用の理解 | ○ | ○ |
| No. |
到達目標 ／Learning Goal |
定期試験 ／Exam. |
レポート課題 | ||||
|---|---|---|---|---|---|---|---|
| 1 | 有限オートマトンの主要な性質、応用の理解 | ○ | |||||
| 2 | 正則表現の主要な性質、応用の理解 | ○ | |||||
| 3 | 文脈自由文法とプッシュダウンオートマトンの主要な性質、応用の理解 | ○ | |||||
|
評価割合（％） ／Allocation of Marks |
100 | ||||||