到達目標
DFA,NFA,εNFA,正則表現が同じ言語を表現することを理解し,相互変換ができる
形式文法の定義や形式文法のチョムスキー階層について例をあげて説明できる。
文脈自由文法とプッシュダウンオートマトンが等価であることが説明できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | DFA,NFA,εNFA,正則表現が等価であることを集合の観点から説明でき,相互変換のアルゴリズムを説明できる。 | DFA,NFA,εNFA,正則表現が等価であることが説明でき,相互変換のアルゴリズムを適用できる。 | DFAとNFAが等価であることが説明できない |
| 評価項目2 | 形式文法の定義に従って文の解析、生成を行うことができ、すべてのチョムスキー階層について判定することができる。 | 形式文法の定義に従って文の解析、生成を行うことができる。
3型文法、2型文法についてチョムスキー階層を判定できる | 与えられた形式文法から文の解析、生成を行うことができない。 |
| 評価項目3 | プッシュダウンオートマトンの動作を理解し、文脈自由文法とプッシュダウンオートマトンの相互変換ができる。 | 文脈自由文法をCNF,GNFへの変換を行うことができる。 | 文脈自由文法の簡略化を行うことができない。 |
学科の到達目標項目との関係
学習・教育到達度目標 D
説明
閉じる
JABEE d-1
説明
閉じる
教育方法等
概要:
オートマトンが情報の表現としての言語を認識したり、関数の計算の複雑さに関する問題を取り扱う上で有効で、情報工学の基礎理論として重要であることを理解する。
授業の進め方・方法:
3年の論理回路の学習項目を今一度確認すること。
授業項目ごとに必ず演習問題を課題として出題する。課題の未提出、白紙での提出は授業に参加していないとみなし
欠席とすることもあるので、真剣に取り組むこと。
合格基準は定期試験60%以上、
最終評価は合格したものについて、定期試験合計80%、演習問題提出状況等で20%で成績を評価する。
演習問題提出状況の評価方法は、期限を守り、題意に沿った解答を各回の100% とし、題意に沿わない解答は１箇所
につき 10% から 20％の減点を行う。
期限を過ぎた提出は 10%から30%の減点とする。また、出題者の想定を越えたすばらしい解答には、10%から 20%の加点をする。
ただし、この演習問題の点数は最終的には 20点を越えないものとする。
再試験は全範囲から 出題する。60% 以上で合格とする。
5年生のコンパイラにつながるコンピュータサイエンスの基礎です
注意点:
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
オートマトンとは,決定性有限オートマトン(DFA)の等価性,状態の等価性(1回) |
有限オートマトン(FA)の定義が判る
|
| 2週 |
非決定性有限オートマトン(NFA)、NFAからDFAへ(1回) |
FAの等価性,状態の等価性を判定できる
|
| 3週 |
FAの簡略化(1回) |
NFAを等価なDFAに、ε-NFAを等価なNFAに変換できる
|
| 4週 |
ε-NFA、εの削除(1回) |
正則表現を等価なNFAに変換できる
|
| 5週 |
正則表現からε-NFAへ(1回) |
FAを状態数最小の等価なFAに変換できる
|
| 6週 |
DFAから正則表現へ(1回) |
DFAを等価な正則表現に変換できる
|
| 7週 |
出力つき 有限オートマトン、形式文法(1回) |
FA、正則表現の等価性を説明できる
|
| 8週 |
後期中間試験:実施する |
|
| 2ndQ |
| 9週 |
文脈自由文法（定義、無効記号の削除） |
CFGの無効記号を削除できる
|
| 10週 |
簡略化1(ε生成規則の削除) |
CFGのε生成規則を削除できる
|
| 11週 |
簡略化2(単位生成規則を削除) |
CFGの単位生成規則を削除できる
|
| 12週 |
チョムスキー標準形(CNF)グライバッハ標準形(GNF)(１回) |
CFGを等価なCNFに変換できる
|
| 13週 |
プッシュダウンオートマトン(PDA)(１回) |
CFGを等価なGNFに変換できる
|
| 14週 |
CFG と PDAの等価性1 |
PDAの動作を理解する、計算状況を示すことができる
|
| 15週 |
CFG と PDAの等価性2 |
CFGを等価なPDAに変換できる
|
| 16週 |
後期期末試験:実施する |
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 4 | |
| オートマトンの概念について説明できる。 | 4 | |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 80 | 0 | 0 | 20 | 0 | 0 | 100 |
| 専門的能力 | 80 | 0 | 0 | 20 | 0 | 0 | 100 |