形式言語理論 (3001)

授業科目基本情報

科目区分 基盤科目 教職科目 指定なし
単位数 1 選択・必修・自由 選択
授業形態 講義 主な使用言語 日本語
開講時期
履修登録期間 2018/05/02~2018/05/16 履修取消期限 2018/05/16

教育プログラム別の履修区分

プログラム名 IS CB BS BN MS CP DS
履修区分
コア科目 C
履修方法 ・基盤科目及び専門科目から12単位以上履修すること。
・情報理工学プログラムでは、コア科目である「形式言語理論」、「プログラミング演習」、「高性能計算基盤」、「ソフトウェア設計論」及び「人工知能」から2科目以上を履修すること。

授業科目概要

担当責任教員 伊藤 実
担当教員 伊藤 実
教育目的/授業目標 形式言語とオートマトン理論に関する基礎的な知識は,情報科学分野において必須と言える素養である。本講義では,その中で最も基本的な正則言語と有限オートマトンに関する基礎的な事柄を理解することを目的とする。正則言語および有限オートマトンは論理設計,通信プロトコル,情報検索,文字列処理等の多くの分野で必要な概念である。
指導方針 計算理論は,情報科学において多くの重要な方法論と結果をもたらした。計算機と同等の能力を持ち,かつ,極限まで簡単化された計算モデルである有限オートマトンを学ぶことで,ハードウェアアーキテクチャの違い,OSの違い,言語の違いにとらわれない,計算機の本質を理解する。同時に,対応する言語のクラスである正則言語も理解する。具体的な項目として,次の順に学んでいく。
 正則言語と有限オートマトン
   ・有限オートマトン(定義,決定性モデルと非決定性モデルの等価性)
   ・正則表現(定義,有限オートマトンとの等価性)
   ・非正則言語(パンピングレンマ)
   ・有限オートマトンの簡単化

クラス情報



表示可能なデータがありません。

授業計画

回数 日付 [時間] テーマ 内容
1 5/10 [2] 諸定義、および、決定性有限オートマトンの導入 まず、本講義で用いる用語・記法の定義を紹介する。次に、本講義の主要なテーマである決定性有限オートマトン(Deterministic Finite Automatonn: DFA)の直観的な説明を行ない、その後、その形式的な定義を説明する。また、正則言語を紹介する。
2 5/14 [2] 非決定性有限オートマトンの導入 非決定性の考え方は、計算理論・アルゴリズム理論において最も重要な概念の一つである。ここでは、その最も単純な形式である非決定性有限オートマトン(Nondeterministic Finite Automaton: NFA)を導入し、非決定性の概念を理解する。
3 5/16 [2] 決定性と非決定性 DFAとNFAの関係について説明する。DFAはNFAの特別な場合なので、NFAの方が高い能力を持つことは自明である。ここでは、任意のNFAから、それと等価なDFAを構成することで、DFAとNFAの言語の受理能力が等価であることを示す。
4 5/18 [2] 正則表現の導入 正則表現は、情報検索において用いられる。ここでは、言語に関する演算を導入し、正則表現の形式的な定義を与える。その後、幾つかの例を用いて、正則表現が表す言語の説明をする。
5 5/22 [2] 正則言語と正則表現 正則表現が表す言語は正則言語であることを示す。具体的には、任意の正則表現から、それが表す言語を受理するNFAを構成する。次に、任意のNFAから、それが受理する言語を表す正則表現を構成する。以上のことから、DFAが受理する言語、NFAが受理する言語、および、正則表現が表す言語は、すべて正則言語であることが結論される。
6 5/24 [2] 非正則言語、および、正則言語に関する判定問題 以上では、正則言語のみを扱ってきた。ここでは、ある言語が正則言語でないことを示すための代表的な手法であるパンピングレンマを紹介する。その後、幾つかの非正則言語の例を、パンピングレンマを用いて示す。次に、正則言語に関する代表的な判定問題を紹介する。
7 5/28 [2] 決定性有限オートマトンの簡単化 任意のDFAから、最簡形と呼ばれる状態数最小のDFAを求める手法を説明する。状態数を減らすことは、回路設計やプロトコル設計において最も重要な処理の一つである。また、NFAでは、同様の手法は適用できないことを示す。
8 5/30 [2] まとめと演習 幾つかの演習問題を解くことで、本講義で説明した内容の理解を深める。

授業日程

回数 日付 時間 講義室 備考
1 5/10 2 L3
2 5/14 2 L3
3 5/16 2 L1
4 5/18 2 L1
5 5/22 2 L1
6 5/24 2 L1
7 5/28 2 L1
8 5/30 2 L1

テキスト・参考書

テキスト モバイルコンピューティング研究室のホームページから該当する科目のテキスト(PDFファイル)をダウンロードすること。特に指定しないが,参考書1,2を読むことを勧める。
参考書 1. 丸岡 章 : 計算理論とオートマトン言語理論,サイエンス社,2005
2. M. Sipser: Introduction to the Theory of Computation Second Edition, Course Technology, 2005
3. J.E.Hopcroft, R.Motwani and J.D.Ullman: Introduction to Automata Theory, Languages, and Computation second edition, Addison-Wesley, 2000
4. 岩間一雄:オートマトン・言語と計算理論,コロナ社,2003

その他

履修条件 アルゴリズムとデータ構造,ブール代数についての知識を持っていることが望ましい。
オフィスアワー Eメールで連絡の上、日時を決める
成績評価の方法と基準 ・5段階(秀・優・良・可・不可)で評価する。
・試験(100%)で評価する。
・正則言語に関する基本的な知識の習得を基準とする。
関連科目 特になし
関連学位 工学
注意事項 特になし

授業関連URL



表示可能なデータがありません。

配布資料



表示可能なデータがありません。