Course Objectives
1.有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できる。
2.正規文法、文脈自由文法、文脈依存文法および句構造文法について説明できる。
3.下降型および上昇型の構文解析法を説明できる。
Rubric
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を正確かつ詳細に説明できる。 | 有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できる。 | 有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できない。 |
| 評価項目2 | 正規文法、文脈自由文法、文脈依存文法および句構造文法について正確かつ詳細に説明できる。 | 正規文法、文脈自由文法、文脈依存文法および句構造文法について説明できる。 | 正規文法、文脈自由文法、文脈依存文法および句構造文法について説明できない。 |
| 評価項目3 | ミーリー型状態遷移機械とムーア型状態遷移機械を正確かつ詳細に説明できる。 | ミーリー型状態遷移機械とムーア型状態遷移機械を説明できる。 | ミーリー型状態遷移機械とムーア型状態遷移機械を説明できない。 |
Assigned Department Objectives
Teaching Method
Outline:
形式言語とオートマトンは、計算機科学を形成する基礎理論であり、情報工学の重要科目として、現 在、Webマイニングやコンパイラ・文書解析に利用されている。 本授業では、オートマトン、すなわち計算機械の数学的モデルに関して、各種モデルとその計算能力について学習する。また、オートマトンと緊密な関係にある形式言語に関して、形式文法による言語の生成能力について学習する。さらに、応用例として、プログラミング言語の正規表現や構文解析法について学習する。
Style:
教科書に沿った講義を行う。オートマトンが受理する言語および文法により生成される言語に関する演習問題をできるだけ多く扱い理解を深める。また、応用例として、プログラミング言語に用いられる正規表現や構文解析の演習を行う。
予習または復習による自学自習の機会に自ら演習問題に取り組むことを推奨する。また、授業時間以外での学修が必要であり、これを課題として課す。
Notice:
本科目は学修単位科目であるので、授業時間以外での学修が必要であり、これを課題として課す。
定期試験(80％)およびレポート(20％)により100点法で評価する。なお、レポート未提出者については評価しない。評価点が60点未満の者に対して、再試験を１回実施し、再試験(80%)、レポート(20%)により、60点を上限として評価する。
評価基準：60点以上を合格とする。
Characteristics of Class / Division in Learning
Course Plan
|
|
|
Theme |
Goals |
| 1st Semester |
| 1st Quarter |
| 1st |
ミーリー型状態遷移機械とムーア型状態遷移機械 |
ミーリー型状態遷移機械とムーア型状態遷移機械を説明できる。
|
| 2nd |
決定性有限状態オートマトンと受理言語 |
決定性有限状態オートマトンとその受理言語を説明できる。
|
| 3rd |
非決定性有限状態オートマトンと受理言語 |
非決定性有限状態オートマトンとその受理言語を説明できる。
|
| 4th |
正規表現 |
正規表現を説明できる。
|
| 5th |
状態数最小のオートマトン |
任意のオートマトンを状態数最小のオートマトンに変形できる。
|
| 6th |
ポンプの補題 |
ポンプの補題を説明できる。
|
| 7th |
正規文法と正規言語 |
正規文法と正規言語を説明できる。
|
| 8th |
決定性プッシュダウンオートマトンと受理言語 |
決定性プッシュダウンオートマトンとその受理言語を説明できる。
|
| 2nd Quarter |
| 9th |
非決定性プッシュダウンオートマトンと受理言語 |
非決定性プッシュダウンオートマトンとその受理言語を説明できる。
|
| 10th |
文脈自由文法と文脈自由言語 |
文脈自由文法と文脈自由言語を説明できる。
|
| 11th |
構文解析 |
構文解析法を説明できる。
|
| 12th |
チューリングマシン |
チューリングマシンを説明できる。
|
| 13th |
線形拘束オートマトン |
線形拘束オートマトンを説明できる。
|
| 14th |
文脈依存文法と文脈依存言語 |
文脈依存文法と文脈依存言語を説明できる。
|
| 15th |
句構造文法と句構造言語 |
句構造文法と句構造言語を説明できる。
|
| 16th |
|
|
Evaluation Method and Weight (%)
| 試験 | レポート | Total |
| Subtotal | 80 | 20 | 100 |
| 専門的能力 | 80 | 20 | 100 |