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

＜授業のねらい＞

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

＜受講にあたっての前提条件＞

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

＜具体的な到達目標＞

与えられた言語を受理する有限オートマトン、プッシュダウンオートマトンの設計ができる。
与えられた有限オートマトン、プッシュダウンオートマトンが受理する言語が求められる。
与えられた言語を生成する文脈自由文法、正規文法、正規表現の設計ができる。
与えられた文脈自由文法、正規文法、正規表現が生成する言語が求められる。

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

　１　形式言語理論とは
　　　形式言語とオートマトンとは何か、および理論的準備を解説する。
　　　準備学習：参考書０章を読んでおく。
　２　有限オートマトンと言語
　　　有限オートマトンの定義を示し、有限オートマトンが受理する言語について解説する。
　　　事前学習：参考書１．１章 p.35-47を読んでおく。
　３　有限オートマトンの構築
　　　与えられた言語を受理する有限オートマトンの設計法について解説する。
　　　事前学習：参考書１．１章 p.48-p.50を読んでおく。
　４　正規表現
　　　正規表現の定義を示し、正規表現が表す言語について解説する。
　　　事前学習：参考書１．３章p.73-77を読んでおく。
　５　プログラミング言語の正規表現
　　　プログラミング言語で使われる正規表現について解説する。
　　　事前学習：LinuxシェルやRubyなどのリファレンスマニュアルを読んでおく。
　６　正規表現の持つ性質
　　　有限オートマトンと正規言語との等価性について解説する。
　　　事前学習：参考書１．３章p.77-88を読んでおく。
　７　正規言語の持つ性質
　　　言語に対する演算と、正規言語が持つ性質について解説する。
　　　事前学習：参考書１．１章p.50-54、１．２章を読んでおく。
　８　形式文法とそのクラス
　　　形式文法の定義とそのクラスについて解説する。
　　　事前学習：参考書２．１章p.115-120を読んでおく。
　９　言語の性質、導出
　　　形式言語による言語の導出について解説する。
　　　事前学習：参考書２．１章p.121-124を読んでおく。
１０　文脈自由文法に対するポンピング補題、演算
　　　文脈自由言語でない言語の例と、ある言語が文脈自由言語でないことを証明する手法、および文脈自由言語に対する演算について解説する。
　　　事前学習：参考書２．３章を読んでおく。
１１　プッシュダウンオートマトン
　　　プッシュダウンオートマトンの定義を示し、プッシュダウンオートマトンが受理する言語について解説する。
　　　事前学習：参考書２．２章p.127-134を読んでおく。
１２　プッシュダウンオートマトンの性質
　　　プッシュダウンオートマトンと文脈自由言語の等価性について解説する。
　　　事前学習：参考書２．２章p.134-144を読んでおく。
１３　計算量理論
　　　計算量およびクラスNPについて解説する。
　　　事前学習：オーダーについて復習しておく。
１４　学習成果の振り返り
　　　事前学習：前回までの総復習を行っておく。

＜成績評価方法＞

定期試験と講義中に行う小テストによる１００点評価で行う。６０点以上を合格とする。
配点の内訳は以下の通りとする。

・定期試験(A)：１００点満点で定期試験期間に行う。再試験・追試験は行わない。
・小テスト(B)：１−１３回目において毎回２０点満点で行い、合算する（２６０点満点）。

評価点＝A*9/10+B/26

＜教科書＞

指定教科書なし

＜参考書＞

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

＜オフィスアワー＞

水曜１限、A-1572研究室で行う。
上記以外の時間を希望する場合はメールで事前にアポイントメントを取ること。
メールアドレス：jt13455@ns.kogakuin.ac.jp

＜学生へのメッセージ＞

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