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

＜学位授与の方針＞

○	1. 基礎知識の習得
◎	2. 専門分野知識の習得
○	3. 汎用的問題解決技能
○	4. 道徳的態度と社会性
○	5. 創成能力

＜授業のねらい＞

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

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

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

＜具体的な到達目標＞

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

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

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

＜成績評価方法＞

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

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

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

＜教科書＞

指定教科書なし

＜参考書＞

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

＜オフィスアワー＞

A-1572研究室で行う。
メールで事前に連絡してアポイントメントを取ること。
メールアドレス：jt13455@ns.kogakuin.ac.jp

＜学生へのメッセージ＞

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