到達目標
有限オートマトン、正規表現、プッシュダウンオートマトン、文脈自由文法の諸概念・性質の理解、特に、有限オートマトンと正規表現ならびにプッシュダウンオートマトンと文脈自由文法の関係を理解、併せて証明手法の習得を到達目標とする。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 有限オートマトンと正規表現 | 有限オートマトンと正規表現の関係を活用できる。 | 基本的な正規言語を有限オートマトンと正規表現で記述できる。 | 基本的な正規言語を有限オートマトンと正規表現で記述できない。 |
| プッシュダウンオートマトンと文脈自由文法 | プッシュダウンオートマトンと文脈自由文法の関係を活用できる。 | 基本的な文脈自由言語をプッシュダウンオートマトンと文脈自由文法で表現できる。 | 基本的な文脈自由言語をプッシュダウンオートマトンと文脈自由文法で表現できない。 |
| 非正規言語と非文脈自由言語 | 複雑な非正規言語・非文脈自由言語の証明ができる。 | 単純な非正規言語・非文脈自由言語の証明ができる。 | 単純な非正規言語・非文脈自由言語の証明ができない。 |
学科の到達目標項目との関係
到達目標 C 1
説明
閉じる
JABEE d-1
説明
閉じる
教育方法等
概要:
理論計算機科学の一つの大きな柱であるオートマトン理論について学ぶ。有限オートマトンと正規表現およびプッシュダウンオートマトンと文脈自由文法の各関係、正規言語の閉包性、ある言語が正規言語、または、文脈自由言語ではないことの証明手法について習得する。
授業の進め方・方法:
基本的に教科書に沿って進める講義が中心であるが、一部輪講形式も取り入れることもある。なお毎回の受講に際しては理解を確実なものとするために、毎回計4時間の予習（教科書の通読）および復習（理解を確実にするためにテキストの演習問題を解くなど）が必要である。
また，テキストの第0章／序論は本科で習った範囲なので講義開始までに確実に習得しておくこと。講義は第１章から始める。
注意点:
最終成績＝ 期末試験
【関連科目】 本 科：集合と論理（2年）、情報数学（3年）、言語処理（5年）；専攻科：自然言語処理（2年）
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
オリエンテーション
形式言語と有限オートマトンおよび決定性有限オートマトン
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
オリエンテーションの後、形式言語の概念、有限オートマトンの例，および決定性有限オートマトンの形式的な定義について学ぶ。
|
| 2週 |
非決定性有限オートマトン
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
非決定性有限オートマトンの直感的概念及び形式的定義について学ぶ。
|
| 3週 |
オートマトンの等価性
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
決定性有限オートマトンと非決定性有限オートマトンが等価であることを証明を通じて理解する。
|
| 4週 |
言語演算と閉包性
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
有限オートマトンにより受理される言語が代表的な言語演算に関して閉じていることを示す。
|
| 5週 |
正規表現
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
正規表現の定義と例を通じて理解を深める。
|
| 6週 |
有限オートマトンの等価性
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
正規表現と有限オートマトンが等価であることを証明する。
|
| 7週 |
非正規言語言語
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
ある言語が有限オートマトンによって決して受理できないことを示す際に使用される反復補題について学ぶ。
|
| 8週 |
演習
【事前事後学習の内容（4時間）】演習の復習と次回の予習 |
第１～７週の内容についての演習を行う。
|
| 4thQ |
| 9週 |
文脈自由文法（１）
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
文脈自由文法を定義し、その例を示す。また例を通じて、その幾つかの性質について学ぶ。
|
| 10週 |
文脈自由文法（２）
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
文脈自由文法の曖昧性や標準形について学ぶ。
|
| 11週 |
プッシュダウンオートマトン
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
プッシュダウンオートマトンの形式的な定義を述べ、その例を示す。
|
| 12週 |
プッシュダウンオートマトンと文脈自由文法の等価性
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
プッシュダウンオートマトンと文脈自由文法が等価であることを証明する。
|
| 13週 |
非文脈自由言語
【事前事後学習の内容（4時間）】指定された演習問題の解答作成と次回の予習 |
ある言語が文脈自由文法によっては決して生成できないことを示す際に使用される反復補題について学ぶ。
|
| 14週 |
演習
【事前事後学習の内容（4時間）】演習の復習と期末試験対策
|
第９～１３週の内容についての演習を行う。
|
| 15週 |
期末試験
|
第１～１４週で学んだことをチェックする．
|
| 16週 |
まとめ
【事前事後学習の内容（2時間）】試験範囲の復習 |
答案の返却を行い，本講義の内容をまとめる。
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 5 | 後1,後6 |
| オートマトンの概念について説明できる。 | 5 | 後2,後3 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 5 | 後9,後15 |
| 正規表現と有限オートマトンの関係を説明できる。 | 5 | 後7,後8 |
評価割合
| 試験 | 課題 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 100 | 0 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 100 | 0 | 0 | 0 | 0 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |