検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れて、検索してください。
応用形式言語
| 平成28年度以前入学者 | 応用形式言語 | ||||
|---|---|---|---|---|---|
| 科目名 平成27年度以前入学者 |
応用形式言語 | ||||
| 教員名 | 戸田 誠之助 | ||||
| 単位数 | 2 | 学年 | 3 | 開講区分 | 文理学部 |
| 科目群 | 情報科学科 | ||||
| 学期 | 前期 | 履修区分 | 選択必修 | ||
| 授業テーマ | 言語の形式的な表現方法を理解する。 |
|---|---|
| 授業のねらい・到達目標 | 2年次後学期「オートマトン」に引き続いて，前半は有限オートマトン，正則表現，正則文法の等価性およびそれらの応用を解説する。後半は，文脈自由文法を中心に，言語の形式的な表現方法とその応用を解説する。授業時間に余裕があるときには，文脈自由文法とプッシュダウンオートマトンの等価性，属性文法とその応用，言語に関するチョムスキー階層などについても解説する。 |
| 授業の方法 | 講義形式。ときおり演習を行い，宿題を課すこともある。 |
| 履修条件 | 2年次科目「オートマトン」を履修していること。有限オートマトンについては既知として授業を始める。 |
| 事前学修・事後学修，授業計画コメント | 2年次「オートマトン」の内容とあわせて，各回の授業内容を復習すること。特に，授業で解説した例題を十分に復習し，授業で示した問の解答を検討すること。 |
| 授業計画 | |
|---|---|
| 1 | 授業ガイダンス，有限オートマトンの復習 |
| 2 | 正則表現 |
| 3 | 正則文法 |
| 4 | 有限オートマトンと正則文法の等価性 |
| 5 | 正則文法と正則表現の等価性 |
| 6 | 有限オートマトンや正則表現の応用：字句解析 |
| 7 | 有限オートマトンや正則表現の応用：パターン検索 |
| 8 | 文脈自由文法の基礎概念 |
| 9 | 文脈自由文法の具体例 |
| 10 | 構文木 |
| 11 | 構文木と導出の関係 |
| 12 | 文脈自由文法の応用：パーサー |
| 13 | 文脈自由文法の応用：マークアップ言語の文法 |
| 14 | 文脈自由文法と言語の曖昧さ |
| 15 | 総合演習 |
| その他 | |
|---|---|
| 教科書 | 講義ノートと配布資料だけで学習ができるように授業を進める。 |
| 参考書 | J. ホップクロフト，R. モトワニ，J．ウルマン 『オートマトン言語理論計算論Ⅰ』 サイエンス社 2003年 第2版 R. モル, A. クフォーリ, M. アービブ 『形式言語理論入門 』 東京電機大学出版局 1995年 徳田 雄洋 『言語と構文解析 （情報数学講座 5 ）』 共立出版 1995年 |
| 成績評価の方法及び基準 | 試験(100%) 宿題を課すこともある。宿題を課したときには，それも加味しながら総合的に評価する。 |
| オフィスアワー | 毎週水曜日１２：１０〜１３：００ |