言語理論

科目基礎情報

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

到達目標

以下の各項目を到達目標とする
(1) 計算機のモデルを理解する。
(2) 形式文法を理解する。
(3) 計算機のモデルと形式文法の関係を理解する。
(4) 抽象的思考ができる。
岐阜高専ディプロマポリシー:(D)

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	有限オートマトン,プッシュダウ ンオートマトン,チューリング機械を理解し，構築することができる	有限オートマトン,プッシュダウ ンオートマトン,チューリング機械を理解している	有限オートマトン,プッシュダウ ンオートマトン,チューリング機械を理解していない
評価項目2	正規表現,文脈自由文法を理解し，作成することができる	正規表現,文脈自由文法を理解している	正規表現,文脈自由文法を理解していない
評価項目3	オートマトンと形式文法の関係を理解し，互いに変換できる	オートマトンと形式文法の関係を理解している	オートマトンと形式文法の関係を理解していない
	オートマトン,チューリング機械,形式文法についての証明がわかり，応用できる	オートマトン,チューリング機械,形式文法についての証明がわかる	オートマトン,チューリング機械,形式文法についての証明がわからない

教育方法等

概要:

計算機科学の基礎となる形式言語とオート マトンの考え方を理解する。

授業の進め方・方法:

教科書に沿って授業をすすめるが,教科書の内容から離れることもあるので講義に集中すること。
英語導入計画：Technical terms

注意点:

演習には積極的に取り組み,指定された課題を提出すること。
授業の内容を確実に身につけるために、予習・復習が必須である。

授業計画

		週	授業内容	週ごとの到達目標
後期
	3rdQ
		1週	言語とは (AL のレベル C)	言語とは，を理解する
		2週	形式言語 (AL のレベル C)	形式言語を理解する
		3週	正規表現 (AL のレベル C)	正規表現を理解する
		4週	有限オートマトン (AL のレベル B)	有限オートマトンを理解する
		5週	非決定性有限オートマトン(AL のレベル C)	直積を理解する 非決定性有限オートマトンを理解する
		6週	有限オートマトンと正規表現 (AL のレベル C)	有限オートマトンと正規表現の関係を理解する
		7週	文脈自由文法 (AL のレベル C)	文脈自由文法を理解する
		8週	中間試験	これまでの理解が不十分な点を復習し理解する
	4thQ
		9週	文脈自由文法の標準形 (AL のレベル C)	文脈自由文法の標準形を理解する
		10週	プッシュダウンオートマトン (AL のレベル C)	プシュダウントートマトンを理解する
		11週	状態数1のプッシュダウンオートマトン (AL のレベル C)	状態数を１にできることを理解する
		12週	プッシュダウンオートマトンと文脈自由文法 (AL のレベル C)	プッシュダウンオートマトンと文脈自由文法の関係を理解する
		13週	チューリング機械 (AL のレベル C)	チューリング機械を理解する
		14週	チューリング機械の停止性 (AL のレベル C)	チューリング機械の停止性を覚える
		15週	NP 完全問題	NP完全問題を覚える。 言語理論の理解が不十分な点を復習し理解する
		16週

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

分類		分野	学習内容	学習内容の到達目標	到達レベル	授業週
専門的能力	分野別の専門工学	情報系分野	システムプログラム	形式言語の概念について説明できる。	4
				オートマトンの概念について説明できる。	4
				形式言語が制限の多さにしたがって分類されることを説明できる。	4
				正規表現と有限オートマトンの関係を説明できる。	4

評価割合

	試験	課題	合計
総合評価割合	200	50	250
得点	200	50	250