形式言語とオートマトン

科目基礎情報

学校	久留米工業高等専門学校	開講年度	令和03年度 (2021年度)
授業科目	形式言語とオートマトン
科目番号	6E20	科目区分	専門 / 選択
授業形態	講義	単位の種別と単位数	学修単位: 2
開設学科	機械・電気システム工学専攻（電気電子工学コース）	対象学年	専1
開設期	前期	週時間数	2
教科書/教材	教科書：岡留剛　著　オートマトンと形式言語入門、森北出版　参考書：Michael Sipser　著　渡辺治　他監訳　計算理論の基礎、共立出版
担当教員	小田 幹雄

到達目標

1.有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できる。
2.正規文法、文脈自由文法、文脈依存文法および句構造文法について説明できる。
3.下降型および上昇型の構文解析法を説明できる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を正確かつ詳細に説明できる。	有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できる。	有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できる。ン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できない。
評価項目2	正規文法、文脈自由文法、文脈依存文法および句構造文法について正確かつ詳細に説明できる。	正規文法、文脈自由文法、文脈依存文法および句構造文法について説明できる。	正規文法、文脈自由文法、文脈依存文法および句構造文法について説明できない。
評価項目3	ミーリー型状態遷移機械とムーア型状態遷移機械を正確かつ詳細に説明できる。	ミーリー型状態遷移機械とムーア型状態遷移機械を説明できる。	ミーリー型状態遷移機械とムーア型状態遷移機械を説明できない。

学科の到達目標項目との関係

JABEE B-1 （ICT電子機器のしくみを理解し説明できる。）

教育方法等

概要:

形式言語とオートマトンは、計算機科学を形成する基礎理論であり、情報工学の重要科目として、現在、Webマイニングやコンパイラ・文書解析に利用されている。 本授業では、オートマトン、すなわち計算機械の数学的モデルに関して、各種モデルとその計算能力について学習する。また、オートマトンと緊密な関係にある形式言語に関して、形式文法による言語の生成能力について学習する。さらに、応用例として、プログラミング言語の正規表現や構文解析法について学習する。

授業の進め方・方法:

教科書に沿った講義を行う。オートマトンが受理する言語および文法により生成される言語に関する演習問題をできるだけ多く扱い理解を深める。また、応用例として、プログラミング言語に用いられる正規表現や構文解析の演習を行う。
予習または復習による自学自習の機会に自ら演習問題に取り組むことを推奨する。また、授業時間以外での学修が必要であり、これを課題として課す。

注意点:

本科目は学修単位科目であるので、授業時間以外での学修が必要であり、これを課題として課す。
定期試験(80％)およびレポート(20％)により100点法で評価する。なお、レポート未提出者については評価しない。評価点が60点未満の者に対して、再試験を１回実施し、再試験(80%)、レポート(20%)により、60点を上限として評価する。
評価基準：60点以上を合格とする。

授業の属性・履修上の区分

ICT 利用

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	ミーリー型状態遷移機械とムーア型状態遷移機械	ミーリー型状態遷移機械とムーア型状態遷移機械を説明できる。
		2週	決定性有限状態オートマトンと受理言語	決定性有限状態オートマトンとその受理言語を説明できる。
		3週	非決定性有限状態オートマトンと受理言語	非決定性有限状態オートマトンとその受理言語を説明できる。
		4週	正規表現	正規表現を説明できる。
		5週	状態数最小のオートマトン	任意のオートマトンを状態数最小のオートマトンに変形できる。
		6週	ポンプの補題	ポンプの補題を説明できる。
		7週	正規文法と正規言語	正規文法と正規言語を説明できる。
		8週	決定性プッシュダウンオートマトンと受理言語	決定性プッシュダウンオートマトンとその受理言語を説明できる。
	2ndQ
		9週	非決定性プッシュダウンオートマトンと受理言語	非決定性プッシュダウンオートマトンとその受理言語を説明できる。
		10週	文脈自由文法と文脈自由言語	文脈自由文法と文脈自由言語を説明できる。
		11週	構文解析	構文解析法を説明できる。
		12週	チューリングマシン	チューリングマシンを説明できる。
		13週	線形拘束オートマトン	線形拘束オートマトンを説明できる。
		14週	文脈依存文法と文脈依存言語	文脈依存文法と文脈依存言語を説明できる。
		15週	句構造文法と句構造言語	句構造文法と句構造言語を説明できる。
		16週

評価割合

	試験	レポート	合計
総合評価割合	80	20	100
専門的能力	80	20	100