言語理論

科目基礎情報

学校	岐阜工業高等専門学校	開講年度	平成28年度 (2016年度)
授業科目	言語理論
科目番号	0132	科目区分	専門 / 選択
授業形態	講義	単位の種別と単位数	学修単位: 1
開設学科	電気情報工学科	対象学年	5
開設期	後期	週時間数	1
教科書/教材	オートマトン・言語と計算理論(岩間一雄・コロナ社)
担当教員	出口 利憲

到達目標

計算機科学の基礎となる形式言語とオート マトンの考え方を理解する。
(1) 計算機のモデルを理解する。
(2) 形式文法を理解する。
(3) 計算機のモデルと形式文法の関係を理解する。
(4) 抽象的思考ができる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	有限オートマトン,プッシュダウ ンオートマトン,チューリング機 械に関する問題を正確(80%)に 解くことができる	有限オートマトン,プッシュダウ ンオートマトン,チューリング機 械に関する問題をほぼ正確(60%)に 解くことができる	有限オートマトン,プッシュダウ ンオートマトン,チューリング機 械に関する問題を解くことができない
評価項目2	正規表現,文脈自由文法に関する 問題を正確(80%)に解くことが できる	正規表現,文脈自由文法に関する 問題をほぼ正確(60%)に解くこ とができる	正規表現,文脈自由文法に関する 問題を解くことができない
評価項目3	オートマトンと形式文法の関係に 関する問題を正確(80%)に解く ことができる	オートマトンと形式文法の関係に 関する問題をほぼ正確(60%)に 解くことができる	オートマトンと形式文法の関係に 関する問題を解くことができない
	オートマトン,チューリング機械,形式文法についての証明に関する問題を正確(80%)に解くことができる	オートマトン,チューリング機械,形式文法についての証明に関する問題をほぼ正確(60%)に解くことができる	オートマトン,チューリング機械,形式文法についての証明に関する問題を解くことができない

教育方法等

概要:

授業の進め方・方法:

教科書に沿って授業をすすめるが,教科書の内容から離れることもあるので講義に集中すること。

注意点:

演習には積極的に取り組み,指定された課題を提出すること。

授業計画

		週	授業内容	週ごとの到達目標
後期
	3rdQ
		1週	言語とは
		2週	形式言語
		3週	正規表現
		4週	有限オートマトン
		5週	非決定性有限オートマトン
		6週	有限オートマトンと正規表現
		7週	文脈自由文法
		8週	中間試験
	4thQ
		9週	文脈自由文法の標準形
		10週	プッシュダウンオートマトン
		11週	状態数1のプッシュダウンオートマトン
		12週	プッシュダウンオートマトンと文脈自由文法
		13週	チューリング機械
		14週	チューリング機械の停止性
		15週	NP 完全問題
		16週

評価割合

	試験	課題	合計
総合評価割合	80	20	100
得点	80	20	100