形式言語とオートマトン

科目基礎情報

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

到達目標

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

ルーブリック

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

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

JABEE C-1 説明 閉じる

教育方法等

概要:
形式言語とオートマトンは、計算機科学を形成する基礎理論であり、情報工学の重要科目として、現 在、Webマイニングやコンパイラ・文書解析に利用されている。 本授業では、オートマトン、すなわち計算機械の数学的モデルに関して、各種モデルとその計算能力について学習する。また、オートマトンと緊密な関係にある形式言語に関して、形式文法による言語の生成能力について学習する。さらに、応用例として、プログラミング言語の正規表現や構文解析法について学習する。
授業の進め方・方法:
教科書に沿った講義を行う。オートマトンが受理する言語および文法により生成される言語に関する演習問題をできるだけ多く扱い理解を深める。また、応用例として、プログラミング言語に用いられる正規表現や構文解析の演習を行う。
予習または復習による自学自習の機会に自ら演習問題に取り組むことを推奨する。また、授業時間以外での学修が必要であり、これを課題として課す。
注意点:
本科目は学修単位科目であるので、授業時間以外での学修が必要であり、これを課題として課す。
定期試験(80%)およびレポート(20%)により100点法で評価する。なお、レポート未提出者については評価しない。評価点が60点未満の者に対して、再試験を1回実施し、再試験(80%)、レポート(20%)により、60点を上限として評価する。
評価基準:60点以上を合格とする。

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

アクティブラーニング
ICT 利用
遠隔授業対応
実務経験のある教員による授業

授業計画

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

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

分類分野学習内容学習内容の到達目標到達レベル授業週
専門的能力分野別の専門工学情報系分野システムプログラム形式言語の概念について説明できる。3前7,前10,前14,前15
オートマトンの概念について説明できる。3前2,前3,前8,前9,前12,前13

評価割合

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