|
専門教育課程 情報工学科
| 授業科目区分 |
科目名 |
単位数 |
科目コード |
開講時期 |
履修方法 |
専門教育課程
専門科目
専門 |
形式言語とオートマトン
Formal Languages and Automata
|
2 |
E517-01 |
2023年度
５期（前学期）
|
修学規程第4条を参照 |
| 授業科目の学習・教育目標 |
| キーワード |
学習・教育目標 |
| 1.有限オートマトン
2.正規言語
3.正規表現
4.文脈自由文法
|
本科目では形式文法と形式言語について学ぶ．とくに正規文法，正規表現および文脈自由文
法を学ぶ．またそれらの言語を処理する種々のオートマトンについても学ぶ．この科目で学
ぶことは言語を表現，処理するための基礎的な知識となる．
|
| 授業の概要および学習上の助言 |
| 本科目では形式言語と形式文法およびそれらを処理する種々のオートマトンを学ぶ．これらの知識は言語を処理，表現する上
での基礎となる．抽象的な議論が多いので，実際に演習問題を解くなど，自主的な学習が望まれる．あらかじめ教科書の該当
するページを読んでおくと授業が理解しやすいであろう． |
| 教科書および参考書・リザーブドブック |
| 教科書：オートマトン・言語理論 [第2版][森北出版]
参考書：指定なし
ﾘｻﾞｰﾌﾞﾄﾞﾌﾞｯｸ：指定なし |
| 履修に必要な予備知識や技能 |
| 離散数学で学ぶ集合とその演算について復習しておくこと．とくに、集合の記法、部分集合、べき集合、順序対について再確
認しておくこと。 |
| 学生が達成すべき行動目標 |
| No. |
学科教育目標
（記号表記） |
|
| ① |
L,M |
チョムスキーの階層が説明できる |
| ② |
L,M |
種々の有限オートマトン間の変換ができる． |
| ③ |
K,L,M |
正規文法，正規言語の定義が説明できる． |
| ④ |
L,M |
有限オートマトンから正規文法への変換、および、逆変換ができる． |
| ⑤ |
L,M |
正規表現の定義が説明できる． |
| ⑥ |
L,M |
文脈自由文法における導出が説明できる． |
| 達成度評価 |
|
|
評価方法 |
| 総合評価割合 |
40 |
60 |
0 |
0 |
0 |
0 |
0 |
100 |
| 指標と評価割合 |
総合評価割合 |
40 |
60 |
0 |
0 |
0 |
0 |
0 |
100 |
| 総合力指標 |
10 |
20 |
0 |
0 |
0 |
0 |
0 |
30 |
| 15 |
20 |
0 |
0 |
0 |
0 |
0 |
35 |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 15 |
20 |
0 |
0 |
0 |
0 |
0 |
35 |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 評価の要点 |
| 評価方法 |
行動目標 |
評価の実施方法と注意点 |
| 試験 |
① |
レ |
おおむね学期の終わり頃に実施する． |
| ② |
レ |
| ③ |
レ |
| ④ |
レ |
| ⑤ |
レ |
| ⑥ |
|
クイズ
小テスト |
① |
レ |
時期，試験範囲等は授業で説明する． |
| ② |
レ |
| ③ |
レ |
| ④ |
レ |
| ⑤ |
レ |
| ⑥ |
|
| レポート |
① |
|
|
| ② |
|
| ③ |
|
| ④ |
|
| ⑤ |
|
| ⑥ |
|
成果発表
(口頭・実技) |
① |
|
|
| ② |
|
| ③ |
|
| ④ |
|
| ⑤ |
|
| ⑥ |
|
| 作品 |
① |
|
|
| ② |
|
| ③ |
|
| ④ |
|
| ⑤ |
|
| ⑥ |
|
| ポートフォリオ |
① |
|
|
| ② |
|
| ③ |
|
| ④ |
|
| ⑤ |
|
| ⑥ |
|
| その他 |
① |
|
|
| ② |
|
| ③ |
|
| ④ |
|
| ⑤ |
|
| ⑥ |
|
| 具体的な達成の目安 |
| 理想的な達成レベルの目安 |
標準的な達成レベルの目安 |
| 形式言語や形式文法の知識を応用してプログラミングを行うこ
とができる．正規表現を使いこなすことができる． |
形式文法や形式言語のついての記述を理解できる． |
| 授業明細 |
| 回数 |
学習内容 |
授業の運営方法 |
学習課題 予習・復習 |
時間：分※ |
| １週 |
シラバスの説明
形式言語と形式文法 |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
60 |
| ２週 |
チョムスキーの階層 |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| ３週 |
決定性有限オートマトン |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| ４週 |
非決定性有限オートマトン |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| ５週 |
有限オートマトンと正規文法 |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| ６週 |
イプシロン動作をもつ非決定性有限オートマトン |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| ７週 |
中間振り返り |
今までを振り返る |
課題はその都度指定する |
90 |
| ８週 |
言語演算 |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| ９週 |
正規表現 |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| １０週 |
正規表現と有限オートマトン |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| １１週 |
正規表現から有限オートマトンへの変換 |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| １２週 |
文脈自由文法 |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
90 |
| １３週 |
あいまいな文法 |
講義，演習と質疑応答，自己
点検 |
課題はその都度指定する |
120 |
| １４週 |
振り返り，期末試験
（実施時期は変更されることがある） |
試験 |
今まで総復習をしておく |
120 |
| １５週 |
試験答案返却と解説，自己点検 |
期末試験の問題解説
アンケート |
試験で解けなかった問題を解ける
ようにする |
120 |
|
一般に、授業あるいは課外での学習では：「知識などを取り込む」→「知識などをいろいろな角度から、場合によってはチーム活動として、考え、推論し、創造する」→「修得した内容を表現、発表、伝達する」→「総合的に評価を受ける、ＧｏｏｄＷｏｒｋ！」：のようなプロセス（一部あるいは全体）を繰り返し行いながら、応用力のある知識やスキルを身につけていくことが重要です。このような学習プロセスを大事に行動してください。
※学習課題の時間欄には、指定された学習課題に要する標準的な時間を記載してあります。日々の自学自習時間全体としては、各授業に応じた時間（例えば2単位科目の場合、予習2時間・復習2時間／週）を取るよう努めてください。詳しくは教員の指導に従って下さい。