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