1. 有限オートマトン，プッシュダウンオートマトンについて理解し設計することができる
2. チューリング機械について理解し設計することができる
3. オートマトンと形式言語との関係について説明することができる
概要:
情報科学分野におけるオートマトンと形式言語ついて学習する．オートマトンは計算機のモデルであり，機械が計算することとは何か，またその計算能力についての理論を与えるための道具である。一方，形式言語は自然言語やプログラミング言語のモデルである。オートマトンと形式文法との関係およびその階層構造について説明でき，チューリング機械等の計算モデルの原理を理解することを到達レベルとする．
授業の進め方・方法:
集合の写像や関係の概念をよく理解しておくこと．関連科目は「アルゴリズムとデータ構造」，「情報数学」，「プログラミング言語論」である．これら科目との連携を意識しながら履修すること．
・課題は前期・後期それぞれ一回以上行い評価する
・オートマトンシミュレータによる実験はPCを利用し実験室で行う
注意点:
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
ガイダンス
オートマトンとは |
オートマトンの概念を理解し，その歴史と役割について説明することができる
|
| 2週 |
語，言語と形式文法 |
語，言語とは何かを理解し，形式文法の数学的定義を説明することができる
|
| 3週 |
有限オートマトン
・決定性有限オートマトンと状態遷移図 |
決定性有限オートマトンの形式的定義を理解し，状態遷移図によっていくつかの言語を表現することができる．
|
| 4週 |
有限オートマトン
・最簡形の決定性有限オートマトン |
同じ言語を表す複数のDFAが存在することを理解し，唯一の最簡形を構築することができる．
|
| 5週 |
有限オートマトン
・非決定性有限オートマトン |
決定性FAと非決定性FAの違いについて説明することができ，NFAとDFAが等価であることを,
NFA・DFA変換を求めることで説明することができる．
|
| 6週 |
有限オートマトン
・有限オートマトンで識別できない言語 |
DFAでは表現できない言語の存在および理由を示すことができる．
|
| 7週 |
演習問題１ |
FAシミュレータを利用しDFA，NFAを設計することができる
|
| 8週 |
演習問題２ |
FAシミュレータを利用しNFAからＤＦＡへの変換アルゴリズムを理解することができる
|
| 2ndQ |
| 9週 |
プッシュダウンオートマトン (PDA）
・ プッシュダウンスタック |
プッシュダウンスタックの構造を理解することができる
|
| 10週 |
プッシュダウンオートマトン (PDA）
・決定性PDA |
決定性PDAの概念を理解し，いくつかの言語について，状態遷移図で示すことができる
|
| 11週 |
プッシュダウンオートマトン (PDA）
・非決定性PDA |
DPDAとNPDAが生成する言語のクラスが異なることを説明することができる
・ある言語についてPDAを設計することができる
・DPDAとNPDAが生成する言語のクラスが異なることを説明することができる
|
| 12週 |
プッシュダウンオートマトン (PDA）
・PDAでは識別できない言語 |
PDAでは表現できない言語の存在および理由を示すことができる
|
| 13週 |
演習問題 |
DPDAが生成できない言語をNPDAで設計できる
|
| 14週 |
チューリング機械 (TM) |
チューリング機械の概念と原理を説明することができる
|
| 15週 |
前期期末試験 |
|
| 16週 |
答案返却・解答解説 |
間違った問題の正答を求めることができる
|
| 後期 |
| 3rdQ |
| 1週 |
チューリング機械 (TM)
・言語の識別機械としてのTM |
FAやPDAで表現できなかった言語に対してTMを設計することができる
|
| 2週 |
チューリング機械 (TM)
・非決定性TM |
多テープTMや非決定性TMなどTMのバリエーションについて説明することができる
|
| 3週 |
チューリング機械 (TM)
・計算機械としてのTM |
単純な計算をTMで設計でき，任意のアルゴリズムがTM上で動作可能なことを理解することができる
|
| 4週 |
演習問題 |
TMシミュレータを利用しTMの設計を行うことができる
|
| 5週 |
形式文法と形式言語
・言語生成装置としての形式文法 |
言語生成装置としての形式文法の役割や概念について説明することができる
|
| 6週 |
形式文法と形式言語
・形式文法のクラスと形式言語のクラス |
句構造文法の４つのクラスの存在について理解することができる
|
| 7週 |
形式文法と形式言語
・正規文法 (RG) と文脈自由文法 (CFG) |
RGとCFGを用いて，いくつかの言語を表すことができる
|
| 8週 |
演習問題（ＦＡからＲＧ） |
ＦＡからＲＧを構成することができる
|
| 4thQ |
| 9週 |
正規表現 |
簡単な言語について，正規表現のパターンを利用することができる
|
| 10週 |
オートマトンと形式文法の関係
・REとFA |
REとFAの言語処理能力が等価であることを理解し，相互の変換を行うことができる
・句構造文法とTMとの関係を説明することができる
|
| 11週 |
オートマトンと形式文法の関係
・FA, REと正規表現 |
正規表現の形式的定義を理解し，言語処理能力がFA等価であることを説明することができる
・句構造文法とTMとの関係を説明することができる
|
| 12週 |
オートマトンと形式文法の関係
・CFGとPDA |
CFGとPDAの言語処理能力が等価であることを理解し，相互の変換を行うことができる
・チョムスキー階層について説明することができる
|
| 13週 |
・正規言語ではない言語の存在 |
ポンプの補題を用いて，ある言語が正規言語ではないことを示すことができる
・チョムスキー階層について説明することができる
|
| 14週 |
・文脈自由言語ではない言語の存在 |
ポンプの補題を用いて，ある言語が文脈自由言語ではないことを示すことができる
・チョムスキー階層について説明することができる
|
| 15週 |
学年末試験 |
|
| 16週 |
試験答案返却・解答解説 |
間違った問題の正答を求めることができる
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | プログラミング言語は計算モデルによって分類されることを説明できる。 | 4 | 後3,後6 |
| 主要な計算モデルを説明できる。 | 4 | 後6 |
| ソフトウェア | アルゴリズムの概念を説明できる。 | 3 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 3 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 2 | |
| システムプログラム | 形式言語の概念について説明できる。 | 4 | 前2 |
| オートマトンの概念について説明できる。 | 4 | 前1,前3 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 後5,後6 |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | 後11 |
| 情報数学・情報理論 | 集合に関する基本的な概念を理解し、集合演算を実行できる。 | 3 | |
| 集合の間の関係(関数)に関する基本的な概念を説明できる。 | 3 | |