| 講師 | 若木利子 |  |
オートマトンと言語理論 |
Automata and Formal Languages |
開講部 | システム理工学部 |
開講学科 | 電子情報システム学科 |
開講学年 | 2年次 |
開講時期 | 後期 |
単位数 | 2 |
単位区分 | 選択 |
系列区分 | 専門 |
講義区分 | 講義 |
教育目標 | G-1 |
| 講師 | 若木利子 | |
| 1. | 言語理論とオートマトンの基礎的知識を習得し、両者の関係を正しく理解する。 |
| 2. | 文脈自由文法を用いて、簡単な形式言語(プログラム言語）の言語設計ができる。 |
| 3. | 有限オートマトンやプッシュダウン・オートマトンの動作と特性を理解し、現実のコンパイラや言語処理系等のソフトウェア開発において、言語理論とオートマトンに関する技術の具体的応用ができる。 |
| 【授業計画】 | 【授業時間外課題（予習および復習を含む）】 | |
| 1. | 「ガイダンス」 ・本科目の概要と目的，成績評価の方法。 ・コンピュータとオートマトンの関係, オートマトンと言語理論の応用例。 「形式言語と自然言語」 ・言語の諸特性(字句，構文，意味)，言語の表現(アルファベット，文）。 | シラバスを確認する。 |
| 2. | 「句構造文法」 ・非終端記号，終端記号，生成規則，開始記号。 ・句構造文法の定義。 | 教科書1.1章 pp.2-4 |
| 3. | 「句構造言語」 ・導出の定義，文形式と文の導出。 ・句構造文法から生成される句構造言語。等価な文法。 | 教科書３章 pp73-80 教科書５章 pp144-146 |
| 4. | 「句構造言語（続き）」 ・句構造言語に関する演習。 「文法の型と言語のクラス」 ・０型，1型，2型, 3型文法の特徴と受理言語のクラス。 | 配布プリントの演習問題を解く。 |
| 5. | 「文法の型と言語のクラス（続き）」 ・文脈依存文法と文脈依存言語，文脈自由文法と文脈自由言語，正規文法と正規言語，Chomsky階層。 ・各クラスの文法と言語に関する演習。 | 教科書３章 pp73-80 教科書４章 pp84-86 教科書５章 pp144-146, pp155-157 |
| 6. | 「文脈自由文法」 ・文の導出と導出木，最左導出と最右導出，ＢＮＦ記法。 ・曖昧な文，曖昧な文脈自由文法，演習。 | 教科書４章 pp84-91 |
| 7. | 「文脈自由文法（続き）」 ・本質的に曖昧な文脈自由言語。 ・文脈自由文法と言語に関する演習。 | 配布プリントの演習問題を解く。 |
| 8. | 「オートマトンのクラスと言語のクラス」 ・チューリング機械，線形有界オートマトン，プッシュダウンオートマトン，有限オートマトン。オートマトンのクラスと受理する言語のクラスの関係。 | 教科書5.2章 教科書5.5.2章 教科書４章 教科書2.2章 |
| 9. | 「有限オートマトン」 ・有限オートマトンの定義。有限制御部，状態遷移関数。 ・有限オートマトンが受理する言語。 | 教科書2.2章 pp.20-26 |
| 10. | 「有限オートマトン（続き）」 ・決定性と非決定性の有限オートマトン。等価なオートマトン。 ・有限オートマトンに関する演習。 | 教科書2.3章。配布プリントの演習問題を解く。 |
| 11. | 「有限オートマトンと正規文法の関係」 ・正規文法から有限オートマトン, 有限オートマトンから正規文法の生成。 ・ε動作を含む有限オートマトン。 | 教科書2.5章 |
| 12. | 「プッシュダウン・オートマトン」 ・プッシュダウン・オートマトンの定義。プッシュダウン・スタック。 ・プッシュダウン・オートマトンが受理する言語。 | 教科書4.8章 |
| 13. | 「プッシュダウン・オートマトンと文脈自由文法の関係」 ・プッシュダウン・オートマトンの決定性/非決定性の定義 ・プッシュダウン・オートマトンと文脈自由文法の関係 ・決定性プッシュダウン・オートマトンと決定性言語の関係 | 教科書4.9章 4.10章 |
| 14. | 文脈自由言語に関する反復定理(uvwxy定理)。 プッシュダウン・オートマトンに関する演習。 | 教科書4.6章。配布プリントの演習問題を解く。 |
| 15. | 学期末試験と解説 | 学期末試験の勉強をする。 |
| ・ | 質問･相談は授業終了時、またはメールでその旨を御連絡下さい。 |
| ・ | 知識活用力を育成する科目 |