到達目標
（１）コンパイラの役割としくみの基礎を理解できる
（２）順序機械および有限オートマトンの基礎を理解できる
（３）正規言語，正規文法の基礎を理解できる
（４）字句解析系，形式言語理論の基礎を理解できる
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | コンパイラの役割としくみの基礎をよく理解できる | コンパイラの役割としくみの基礎を理解できる | コンパイラの役割としくみの基礎を理解できない |
| 評価項目2 | 順序機械および有限オートマトンの基礎をよく理解できる | 順序機械および有限オートマトンの基礎を理解できる | 順序機械および有限オートマトンの基礎を理解できない |
| 評価項目3 | 正規言語，正規文法の基礎をよく理解できる | 正規言語，正規文法の基礎を理解できる | 正規言語，正規文法の基礎を理解できない |
| 評価項目4 | 字句解析系，形式言語理論の基礎をよく理解できる | 字句解析系，形式言語理論の基礎を理解できる | 字句解析系，形式言語理論の基礎を理解できない |
学科の到達目標項目との関係
学習・教育到達度目標 J2
説明
閉じる
学習・教育到達度目標 J4
説明
閉じる
学習・教育到達度目標 J5
説明
閉じる
教育方法等
概要:
この授業では，コンパイラのみならず情報科学の基礎をなす有限オートマトンを中心に，形式言語理論，字句解析系，構文解析系の概要を知ることを目的とする．有限オートマトンは，本来計算機を抽象化して得られる数学的モデルである．本科目では，順序機械、決定性有限オートマトン、非決定性有限オートマトンについて述べ、有限オートマトンを用いた字句解析系，形式言語理論の基礎を説明する．
本科目は，情報処理学会が策定したIPSJ-SE推奨カリキュラムの「形式言語と計算理論」の教育内容に準拠している（IEEE/ACM-CCSEカリキュラムにも対応）．
授業の進め方・方法:
到達目標(1)～(3)の到達度を定期試験80％，課題レポート，小テスト20％の割合で評価し，60点以上を合格とする．なお，本科目は授業・自学ノートの提出とそのノートの内容が指定した水準以下の場合は，課題レポートの評価にかかわらず科目成績を３５点以下とする．さらに，卒業追認試験については，成績評価が３６点以上の者について申請があった場合にのみ受験を認める．
注意点:
学修単位科目であり，１回の講義（90分）あたり180分以上の予習・復習をしているものとして講義・演習を進める．
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
１．序論（その１）
コンパイラの概要と形式言語について概要を解説する．また，数学的基礎について概説する．
|
|
| 2週 |
１．序論（その２）
数学的基礎について引き続き解説を行い，言語についての定義を示す．
|
|
| 3週 |
２．有限オートマトンと正規表現（その１）
離散時間システム，ミーリー型順序機械について解説を行う．
|
|
| 4週 |
２．有限オートマトンと正規表現（その２）
ミーリー型順序機械とその状態簡約，ムーア型順序機械について説明を行う．
|
|
| 5週 |
２．有限オートマトンと正規表現（その３）
順序機械を発展させた有限オートマトンの概要について解説する．とくに状態遷移関数について説明する．
|
|
| 6週 |
２．有限オートマトンと正規表現（その４）
チューリングマシンについて触れ，正規言語について解説する．
|
|
| 7週 |
２．有限オートマトンと正規表現（その５）
有限オートマトンの等価性判定アルゴリズムについて解説を行う．
|
なお，本科目では総合評価の他に，課題レポート・自学ノートの評価が１００点満点中６０点以上であることを合格の条件とする．また，講義ノートとは別に所定の自学ノートを提出しないと期末試験の受験を認めない．
|
| 8週 |
中間試験
第１週から第７週までの内容で中間試験を実施する
|
|
| 2ndQ |
| 9週 |
２．有限オートマトンと正規表現（その６）
非決定性有限オートマトンの概要について説明する．
|
|
| 10週 |
２．有限オートマトンと正規表現（その７）
非決定性有限オートマトン，部分集合構成法について解説を行う．
|
|
| 11週 |
２．有限オートマトンと正規表現（その８）
空動作を有する非決定性有限オートマトンについて解説を行う．
|
|
| 12週 |
２．有限オートマトンと正規表現（その９）
正規表現と空動作を有する非決定性有限オートマトン，正規言語と非正規言語について解説を行う．
|
|
| 13週 |
２．有限オートマトンと正規表現（その１０）
形式文法，構文，正規文法について概要を解説する．
|
|
| 14週 |
３．文脈自由文法とlexの紹介
文脈自由文法，lexプログラムの書き方などを解説する．
|
|
| 15週 |
期末試験
９～１４回目の内容について期末試験を実施する．
|
|
| 16週 |
試験の解答と解説
期末試験の解答と解説を行う．
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 3 | |
| オートマトンの概念について説明できる。 | 3 | |
| コンパイラの役割と仕組みについて説明できる。 | 3 | |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 3 | |
| 正規表現と有限オートマトンの関係を説明できる。 | 3 | |
評価割合
| 定期試験 | 発表 | 相互評価 | 課題レポート，小テスト | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 80 | 0 | 0 | 20 | 0 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 80 | 0 | 0 | 20 | 0 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |