到達目標
有限オートマトン、正規表現、プッシュダウンオートマトン、文脈自由文法の諸概念・性質の理解、特に、有限オートマトンと正規表現ならびにプッシュダウンオートマトンと文脈自由文法の関係を理解、併せて証明手法の習得を到達目標とする。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 有限オートマトンと正規表現の関係を活用できる。 | 基本的な正規言語を有限オートマトンと正規表現で記述できる。 | 基本的な正規言語を有限オートマトンと正規表現で記述できない。 |
| プッシュダウンオートマトンと文脈自由文法の関係を活用できる。 | 基本的な文脈自由言語をプッシュダウンオートマトンと文脈自由文法で表現できる。 | 基本的な文脈自由言語をプッシュダウンオートマトンと文脈自由文法で表現できない。 |
| 複雑な非正規言語・非文脈自由言語の証明ができる。 | 単純な非正規言語・非文脈自由言語の証明ができる。 | 単純な非正規言語・非文脈自由言語の証明ができない。 |
学科の到達目標項目との関係
教育方法等
概要:
理論計算機科学の一つの大きな柱であるオートマトン理論について学ぶ。有限オートマトンと正規表現およびプッシュダウンオートマトンと文脈自由文法の各関係、正規言語の閉包性、ある言語が正規言語、または、文脈自由言語ではないことの証明手法について習得する。
授業の進め方・方法:
講義が中心であるが、一部輪講形式も取り入れる予定である。また、その理解を確実なものとするために、演習問題等による家庭での自学自習は必須である。
注意点:
【関連科目】 本 科：集合と論理（2年）、情報数学（3年）、言語処理（5年）；専攻科：自然言語処理（2年）
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
オリエンテーション
形式言語と有限オートマトン |
オリエンテーションの後、形式言語の概念、有限オートマトンの例について学ぶ。
|
| 2週 |
決定性有限オートマトン |
決定性有限オートマトンの形式的な定義及び計算の形式的定義について学ぶ。
|
| 3週 |
非決定性有限オートマトン |
非決定性有限オートマトンの直感的概念及び形式的定義について学ぶ。
|
| 4週 |
オートマトンの等価性 |
決定性有限オートマトンと非決定性有限オートマトンが等価であることを証明を通じて理解する。
|
| 5週 |
言語演算と閉包性 |
有限オートマトンにより受理される言語が代表的な言語演算に関して閉じていることを示す。
|
| 6週 |
正規表現 |
正規表現の定義と例を通じて理解を深める。
|
| 7週 |
正規表現と有限オートマトンの等価性（１） |
正規表現と有限オートマトンが等価であることを証明する。
|
| 8週 |
正規表現と有限オートマトンの等価性（２） |
前回の証明の続きと両者が等価である例について学ぶ。
|
| 4thQ |
| 9週 |
非正規言語言語 |
ある言語が任意の有限オートマトンによって決して受理できないことを示す際に使用される反復補題について学ぶ。
|
| 10週 |
文脈自由文法 |
文脈自由法を定義し、その例を示す。また例を通じて、その幾つかの性質について学ぶ。
|
| 11週 |
プッシュダウンオートマトン |
プッシュダウンオートマトンの形式的な定義を述べ、その例を示す。
|
| 12週 |
プッシュダウンオートマトンと文脈自由文法の等価性（１） |
プッシュダウンオートマトンと文脈自由文法が等価であることを証明する。
|
| 13週 |
プッシュダウンオートマトンと文脈自由文法の等価性（２） |
前回の証明の続きと両者が等価である例について学ぶ。
|
| 14週 |
プッシュダウンオートマトンで受理できない言語 |
プッシュダウンオートマトンで受理できない言語
|
| 15週 |
非文脈自由言語と形式言語の階層性 |
文脈自由言語に対する反復補題について学び、条件の度合いによる形式言語の階層性について学ぶ。
|
| 16週 |
期末試験 |
有限オートマトン、正規言語、プッシュダウンオートマトン、文脈自由言語について理解できているかを確認する。
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 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 |