到達目標
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% 以上で合格とする。
注意点:
論理回路ではすでに 出力付き有限オートマトンを扱っています。状態遷移表や状態遷移グラフなどについて確認しておいてください。
4年生のコンパイラにつながるコンピュータサイエンスの基礎です。
本科目は「授業時間外の学修を必要とする科目」である．授業時間外の学修（準備学習を含む）については科目担当教員から指示するので，必ず予習・復習等をおこなうこと．
事前に行う準備学習：各回の講義内容の復習をおこなうこと．
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
オートマトンとは,決定性有限オートマトン(DFA)の等価性 |
準備（集合、組、直積集合、冪集合、閉包についての確認）
決定性有限オートマトン(DFA)の定義、動作を説明できる。FAの等価性を判定できる
|
| 2週 |
状態の等価性、狭義のDFA,広義のDFA |
DFAの状態対の等価性を判定できる。狭義のDFAについて説明できる
|
| 3週 |
DFAの最小化 |
DFAを状態数最小の等価なDFAに変換できる
|
| 4週 |
非決定性有限オートマトン(NFA)、NFAからDFAへ、ε-NFAの動作、εの削除 |
非決定性有限オートマトン(NFA)の定義、動作を説明できる
NFAを等価なDFAに、ε-NFAを等価なNFAに変換できる
|
| 5週 |
正則表現からε-NFAへ |
正則表現を等価なε-NFAへ変換できる
|
| 6週 |
DFAから正則表現へ |
DFAを等価な正則表現に変換できる
|
| 7週 |
形式文法 |
形式文法のクラスについて理解し、適切なクラスを判定できる
|
| 8週 |
後期中間試験:実施する |
|
| 2ndQ |
| 9週 |
文脈自由文法（定義、無効記号の削除） |
CFGの無効記号を削除できる
|
| 10週 |
簡略化1(ε生成規則の削除) |
CFGのε生成規則を削除できる
|
| 11週 |
簡略化2(単位生成規則を削除) |
CFGの単位生成規則を削除できる
|
| 12週 |
チョムスキー標準形(CNF) |
CFGを等価なCNFに変換できる
|
| 13週 |
グライバッハ標準形(GNF) |
CNFを等価なGNFに変換できる
|
| 14週 |
プッシュダウンオートマトン
CFG と PDAの等価性1 |
PDAの動作を理解する、計算状況を示すことができる
CFGを等価なPDAに変換できる
|
| 15週 |
CFG と PDAの等価性2 |
PDAを等価なCFGに変換できる
|
| 16週 |
後期期末試験:実施する |
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 4 | 前7,前9 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 前9 |
| オートマトンの概念について説明できる。 | 4 | 前1,前2,前3,前4 |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | 前5,前6 |
| 情報数学・情報理論 | 集合に関する基本的な概念を理解し、集合演算を実行できる。 | 4 | 前1 |
| 集合の間の関係(関数)に関する基本的な概念を説明できる。 | 4 | 前1 |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 80 | 0 | 0 | 20 | 0 | 0 | 100 |
| 専門的能力 | 80 | 0 | 0 | 20 | 0 | 0 | 100 |