形式言語とオートマトン |
Automata and Formal Languages |
開講部 | 工学部 |
開講学科 | 情報工学科 |
開講学年 | 1年次 |
開講時期 | 後期 |
単位数 | 2 |
単位区分 | 選択 |
系列区分 | 専門 |
講義区分 | 講義 |
教育目標 | B-1 |
| 教授 | 中島毅 |
| 1. | 順序機械を読み記述できる (授業計画の２に対応) |
| 2. | DFA、NFA、ε-NFAを理解し受理する／しない語を判断できる (授業計画の３〜６に対応) |
| 3. | DFA→正規表現→ε-NFA→NFA→DFAの変形ができ (授業計画の４〜７に対応)、 DFAの最小化ができる (授業計画の９〜１０に対応) |
| 4. | 構文木を理解し中置、ポーランド、逆ポーランド記法間の変換ができる (授業計画の1２に対応) |
| 5. | 構文木を介し、文脈自由文法とプッシュダウンオートマトンの等価性を理解でき(授業計画の1３に対応)、BNFから構文図式への変換ができる (授業計画の１１に対応) |
| 【授業計画】 | 【授業時間外課題（予習および復習を含む）】 | |
| 1. | 概要： オートマトンと言語、チョムスキの４階層 | シラバスの閲覧 |
| 2. | 形式言語と帰納的表現： 語、言語、クリーネ閉包 順序機械： ミーリ機械、ムーア機械 | 教科書：pp.22-25，32-39，83-88 |
| 3. | 言語の受理、決定性オートマトン（DFA） | 教科書:pp.88-95 |
| 4. | 正規表現、正規方程式（DFAからの変換） | 教科書:pp.96-104 |
| 5. | 非決定性オートマトン（NFA）： 定義とDFAへの変換 | 教科書:pp.105-109 |
| 6. | ε-NFA： 定義とNFAへの変換 | 教科書:pp.109-112 |
| 7. | 正規表現からε-NFA、NFA、DFA | 教科書:pp.112-115 |
| 8. | 中間テスト、講評 | 教科書：上記2-7の範囲 |
| 9. | 最小化（１）：Myhill-Nerodeの定理、同値類 | 教科書:pp.116-119 |
| 10. | 最小化（２）：最小化と演習 | 教科書:pp.121-123 |
| 11. | 形式言語とＢＮＦ記法：メタ言語、構文図式 | 教科書:pp. 43-47 |
| 12. | 形式言語としての数式と構文木 ・中置、ポーランド、逆ポーランド記法 | 教科書:pp.41-43，78-80，140-144 |
| 13. | 文脈自由文法とプッシュダウンオートマトン | 教科書:pp.145-153，125-131 |
| 14. | 復習と応用的話題 | 教科書:上記2-7,9-14の範囲 |
| 15. | 期末テストと解説 | 教科書:上記2-7,9-14の範囲 |
| ・ | 火曜１６：１０ |
| ・ | 対課題基礎力を育成する科目 |