オートマトン

科目基礎情報

学校	函館工業高等専門学校	開講年度	2017
授業科目	オートマトン
科目番号	0346	科目区分	専門 / 必修
授業形態	授業	単位の種別と単位数	履修単位: 2
開設学科	生産システム工学科	対象学年	4
開設期	通年	週時間数	2
教科書/教材	オートマトン・言語理論の基礎，米田政明 他，近代科学社（2003）
担当教員	河合 博之

到達目標

1. 有限オートマトン，プッシュダウンオートマトンについて理解し設計することができる
2. チューリング機械について理解し設計することができる
3. オートマトンと形式言語との関係について説明することができる

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	ＮＦＡをＤＦＡに変換することでその等価性を理解することができる	簡単な言語をオートマトンで表現することができる	簡単な言語をオートマトンで表現することができない
評価項目2	計算機械としてチューリング機械を設計することができる	簡単な言語を非決定チューリング機械を用いて設計することができる	簡単な言語を非決定チューリング機械を用いて設計することができない
評価項目3	言語の階層構造を理解し，正規言語ではない言語の存在を証明することができる	正規文法，文脈自由文法および文脈依存文法の定義を理解することができる	正規文法，文脈自由文法および文脈依存文法の定義を理解することができない

教育方法等

概要:

情報科学分野におけるオートマトンと形式言語ついて学習する．オートマトンは計算機のモデルであり，機械が計算することとは何か，またその計算能力についての理論を与えるための道具である。一方，形式言語は自然言語やプログラミング言語のモデルである。オートマトンと形式文法との関係およびその階層構造について説明でき，チューリング機械等の計算モデルの原理を理解することを到達レベルとする．

授業の進め方・方法:

集合の写像や関係の概念をよく理解しておくこと．関連科目は「アルゴリズムとデータ構造」，「情報数学」，「プログラミング言語論」である．これら科目との連携を意識しながら履修すること．

・課題は前期・後期それぞれ一回以上行い評価する
・オートマトンシミュレータによる実験はPCを利用し実験室で行う

注意点:

JABEE教育到達目標評価　定期試験100％（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週	試験答案返却・解答解説	・間違った問題の正答を求めることができる

モデルコアカリキュラムの学習内容と到達目標

分類		分野	学習内容	学習内容の到達目標	到達レベル	授業週
専門的能力	分野別の専門工学	情報系分野	プログラミング	プログラミング言語は計算モデルによって分類されることを説明できる。	3
			ソフトウェア	アルゴリズムの概念を説明できる。	3
				与えられたアルゴリズムが問題を解決していく過程を説明できる。	3
				同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	2
				時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。	2
			システムプログラム	形式言語の概念について説明できる。	5
				オートマトンの概念について説明できる。	5
			情報数学・情報理論	集合に関する基本的な概念を理解し、集合演算を実行できる。	3
				集合の間の関係(関数)に関する基本的な概念を説明できる。	3

評価割合

	試験	発表	相互評価	態度	ポートフォリオ	合計
総合評価割合	100	0	0	0	0	100
基礎的能力	0	0	0	0	0	0
専門的能力	100	0	0	0	0	100
分野横断的能力	0	0	0	0	0	0