オートマトンと形式言語（Automata and Formal Languages）[5A18]

＜授業のねらい及び具体的な達成目標＞

生成文法・形式言語・オートマトン理論の概要を理解する

＜授業計画及び準備学習＞

・数学の基礎知識の確認
・オートマトン理論・計算量理論の概要（2〜3回）
・有限状態オートマトン（☆）
・正規表現（正則表現）（☆）
・文脈自由言語（☆）
・プッシュダウンオートマトン（☆）
☆演習も含む
時間に余裕があれば
・チューリング機械
・決定不能性
・計算量

＜成績評価方法及び水準＞

試験による
100点満点換算で60点以上で合格とする
授業中の演習問題の回答状況により加点することがある
授業態度が悪い場合は減点することがある

＜教科書＞

E. キンバーほか　著「計算論への入門--オートマトン・言語理論・チューリング機械--」ピアソン・エデュケーション

＜参考書＞

J. ホップクロフト ほか　著　「オートマトン言語理論 計算論〈1〉」サイエンス社

＜オフィスアワー＞

事前にメール等で連絡してください

＜学生へのメッセージ＞

・集合と写像
・数列
・同値関係
・グラフと部分グラフ、有効グラフ
・帰納的定義と数学的帰納法による証明
の知識は必須です。

2年生で先行履修を希望する場合は
・情報数学I、II
・離散数学
の単位を取得しておくこと。

このページの著作権は学校法人工学院大学が有しています。 Copyright(c)2009 Kogakuin University. All Rights Reserved.