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