| 授業の目標と概要 |
4年のオートマトンの授業では オートマトンが情報の表現としての言語を認識したり、
関数の計算の複雑さに関する問題を取り扱う上で有効で、情報工学の基礎理論として重要であることを理解する。
|
履修上の注意
(準備する用具・
前提とする知識等)
|
3年の論理回路の学習項目を今一度確認すること。
授業項目ごとに必ず演習問題を課題として出題する。課題の未提出、白紙での提出は授業に参加していないとみなし
欠席とすることもあるので、真剣に取り組むこと。
|
| 到達目標 |
有限オートマトンと正則言語の等価性、プッシュダウンオートマトンと文脈自由言語の等価性と形式言語のクラスに
ついて説明できる。
|
| 成績評価方法 |
合格基準は定期試験60%以上、
最終評価は合格したものについて、定期試験合計80%、演習問題提出状況等で20%で成績を評価する。
演習問題提出状況の評価方法は、期限を守り、題意に沿った解答を各回の100% とし、題意に沿わない解答は１箇所
につき 10% から 20％の減点を行う。
期限を過ぎた提出は 10%から30%の減点とする。また、出題者の想定を越えたすばらしい解答には、10%から 20%の加点をする。
ただし、この演習問題の点数は最終的には 20点を越えないものとする。
再試験は全範囲から 出題する。60% 以上で合格とする。
|
| テキスト・参考書 |
(教科書)計算理論の基礎 原著第2版 1.オートマトンと言語 Michael Sipser 著、共立出版
(参考書)オートマトン・言語理論 富田悦次、横森 貴 共著 森北出版
(参考書)オートマトン・言語の基礎 米田政明 他 近代科学社
(参考書)言語理論とオートマトン ホップクロフト、ウルマン共著 野崎昭弘、木村泉共訳 サイエンス社
|
| メッセージ |
5年生のコンパイラにつながるコンピュータサイエンスの基礎です
|
| 授業の内容 |
授業項目 | 授業項目ごとの達成目標 |
オートマトンとは,決定性有限オートマトン(DFA)の等価性,状態の等価性(1回)
非決定性有限オートマトン(NFA)、NFAからDFAへ(1回)
FAの簡略化(1回)
ε-NFA、εの削除(1回)
正則表現からε-NFAへ(1回)
DFAから正則表現へ(1回)
出力つき 有限オートマトン、形式文法(1回)
|
有限オートマトン(FA)の定義が判る
FAの等価性,状態の等価性を判定できる
NFAを等価なDFAに、ε-NFAを等価なNFAに変換できる
正則表現を等価なNFAに変換できる
FAを状態数最小の等価なFAに変換できる
DFAを等価な正則表現に変換できる
FA、正則表現の等価性を説明できる
ムーア機械、ミーリー機械を構成できる
0型から3型および線形文法の区別ができる。
形式文法における文の生成、解析について理解できる
|
| 後期中間試験 |
実施する
|
文脈自由文法（CFG）(１回)
簡略化(2回)
チョムスキー標準形(CNF)グライバッハ標準形(GNF)(１回)
プッシュダウンオートマトン(PDA)(１回)
CFG と PDAの等価性(2回)
|
CFGの無効記号を削除できる
CFGのε生成規則を削除できる
CFGの単位生成規則を削除できる
CFGを等価なCNFに変換できる
CFGを等価なGNFに変換できる
PDAの動作を理解する、計算状況を示すことができる
CFGを等価なPDAに変換できる
PDAを等価なGNFに変換できる
|
| 後期期末試験 |
実施する
|