| 授業科目名（和文） ［Course］ |
形式言語理論 |
| 授業科目名（英文） ［Course］ |
Formal Language Theory |
| 学部（研究科） ［Faculty］ |
情報系工学研究科 |
| 学科（専攻） ［Department］ |
電子情報通信工学専攻 |
| 担当教員（○：代表教員） [Principle Instructor(○) and Instructors] |
○國島 丈生 自室番号（2610）、電子メール（kunishi**c.oka-pu.ac.jp） ※利用の際は,** を @に置き換えてください |
| 単位数 ［Point(Credit)］ |
2単位 |
| 対象学生 ［Eligible students］ |
1?2年次生 |
| 授業概略と目標 ［Course description and Objects］ |
言語理論とオートマトン理論のうち、情報科学の理論?応用の両面で重要になっている項目について講述する。有限オートマトンと正則表現、文脈自由文法、プッシュダウンオートマトン、木オートマトンと木正則表現などを取り上げる。 |
| 到達目標 ［Learning Goal］ |
1. 有限オートマトンの主要な性質、応用などについて理解する。 2. 正則表現の主要な性質、応用などについて理解する。 3. 文脈自由文法とプッシュダウンオートマトンの主要な性質、応用などについて理解する。 |
| 履修上の注意 ［Notes］ |
履修の要件:集合、数学的帰納法など、情報数学の基本事項について理解していること。 |
| 授業計画とスケジュール ［Course schedule］ |
1. 導入 2. 決定性有限オートマトン(DFA) 3. 非決定性有限オートマトン(NFA)とDFA 4. 正則表現 5. 正則表現の応用 6. 正則表現と有限オートマトンの等価性 7. 正則言語とその性質 8. 有限オートマトンの状態数最小化 9. 文脈自由文法(CFG) 10. 文脈自由文法の応用 11. プッシュダウンオートマトン(PDA) 12. CFGとPDAの等価性 13. 文脈自由言語とその性質 14. 木オートマトンとその応用 15. 木正則表現とその応用 |
| 成績評価方法と基準 ［Grading policy (Evaluation)］ |
定期試験（もしくはそれに相当するレポート課題）80%、学習態度20%によって総合的に判定する。 |
| 教科書 ［Textbook］ |
教科書: 「オートマトン 言語理論 計算論I (第2版)」, J. ホップクロフトほか, サイエンス社 参考書: 使用しない |
| 自主学習ガイド及び キーワード ［Self learning］ |
講義時間の制約上、証明の詳細は省略することが多いが、言語理論を深く理解するには教科書に掲載されている証明も時間をかけて読んでみることが望ましい。 |
| 開講年度 ［Year of the course］ |
26 |