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

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

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

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

１数学の基礎知識の確認
　準備学習：教科書第1章の内容を理解しておく
２オートマトン理論・計算量理論の概要（１：形式言語とは、オートマトンとは、チョムスキーの階層、オートマトンと言語のクラス）
　準備学習：（）内に挙げたキーワードについて調べておく
３オートマトン理論・計算量理論の概要（２：チューリング機械と計算量、PとNP）
　準備学習：（）内に挙げたキーワードについて調べておく
４決定性有限オートマトン
　準備学習：教科書第2.1節に目を通し、疑問点を整理しておく
５非決定性有限オートマトン
　準備学習：教科書第2.2および2.3節に目を通し、疑問点を整理しておく
６正則表現（正規表現）
　準備学習：教科書第2.4節に目を通し、疑問点を整理しておく
７正則性と正則言語の演算
　準備学習：教科書第2.5および2.6節に目を通し、疑問点を整理しておく
８状態数最小化問題
　準備学習：教科書第2.7節に目を通し、疑問点を整理しておく
９教科書第2章の演習
　準備学習：教科書52ページから66ページの演習問題（★のつかないもの）を解いておく
１０文脈自由言語と構文解析
　準備学習：教科書第3.1および3.2節に目を通し、疑問点を整理しておく
１１文脈自由言語の演算とチョムスキー標準形
　準備学習：教科書第3.5から3.7節に目を通し、疑問点を整理しておく
１２プッシュダウンオートマトン
　準備学習：教科書第3.3および3.4節に目を通し、疑問点を整理しておく
１３プッシュダウンオートマトンと決定性
　準備学習：教科書第3.8節に目を通し、疑問点を整理しておく
１４教科書第3章の演習
　準備学習：教科書111ページから120ページの演習問題（★のつかないもの）を解いておく
１５学習成果の確認（試験）
　準備学習：前回までの総復習

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

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

＜教科書＞

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

＜参考書＞

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

＜オフィスアワー＞

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

＜学生へのメッセージ＞

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

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

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