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

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

プログラミング言語や自然言語処理の基本となる生成文法・形式言語・オートマトン理論に関する基礎知識を習得する。

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

　１　形式言語理論とは何か、および理論的準備
　　　事前学習　教科書０章
　２　有限オートマトンと言語
　　　事前学習　教科書１．１章
　３　有限オートマトンの構築
　　　事前学習　教科書１．１章
　４　正規表現
　　　事前学習　教科書１．３章
　５　有限オートマトンの認識する言語の性質
　　　事前学習　教科書１．１章
　６　有限オートマトンから正規表現へ
　　　事前学習　教科書１．２章
　７　正規言語の性質
　　　事前学習　教科書１．３、１．４章
　８　形式文法とそのクラス
　　　事前学習　教科書２．１章
　９　導出
　　　事前学習　教科書２．１章
１０　認識・構文解析
　　　事前学習　教科書２．１章
１１　文脈自由文法・言語の性質
　　　事前学習　教科書２．１章
１２　言語に対する演算
　　　事前学習　教科書２．３章
１３　プッシュダウンオートマトン
　　　事前学習　教科書２．２章
１４　計算量理論
　　　事前学習　ＰとＮＰについて
１５　試験　

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

講義中の小テスト、最終試験および出席により判定する。再試験・追試験などは行わない。

＜教科書＞

Michael Sipser著　「計算理論の基礎　原著第２版　１　オートマトンと言語」　共立出版

＜参考書＞

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

＜オフィスアワー＞

未定。
事前にメールでアポイントメントを取ること。

＜学生へのメッセージ＞

難しい数学を使う訳ではありませんが、内容はやさしくありません。演習問題をこつこつ解くことでのみ、習得できる内容です。

＜備考＞

集合・写像・数列・グラフ理論・数学的帰納法に関する知識を必要とする。
情報数学Ｉおよび離散数学の単位を取得しておくこと。

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