2021年度学院等開講科目情報理工学院数理・計算科学系

オートマトンと数理言語論

開講元: 数理・計算科学系
担当教員: 伊東利哉 / 田中圭介
授業形態: 講義
メディア利用科目: -
曜日・時限 (講義室): 月3-4 (W833) / 木3-4 (W833)
クラス: -
科目コード: MCS.T214
単位数: 200
開講時期: 2021年度
開講クォーター: 2Q
シラバス更新日: 2025年7月10日
使用言語: 日本語

シラバス

授業の目的（ねらい）、概要

計算可能性の理論、計算複雑さの理論の基礎として、有限オートマトンおよび文脈自由文法について学びます。これを通して、計算機のハードウェア、ソフトウェアに関する基本的な数学的概念を理解します。具体的には、文字列と言語、有限オートマトン、非決定計算、正規表現、文脈自由文法、プッシュダウン・オートマトン、ポンピング補題を扱います。

到達目標

本講義を履修することによって以下を理解します。
1) 言語理論における数学的要素
2) 正規言語のモデルと性質
3) 文脈自由言語のモデルと性質

キーワード

オートマトン、言語、文字列、有限オートマトン、非決定計算、正規表現、文脈自由文法、プッシュダウン・オートマトン、ポンピング補題

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

授業は通常の講義の他に演習形式の講義があります。通常の講義3ないし4回につき1回の割り合いで演習形式の講義を行います。そこでは、通常の講義中に扱えなかった内容や小テストについて説明します。授業では毎回、その回の内容、または、それ以前の回の内容について小テストを出します。

授業計画・課題

	授業計画	課題
第1回	講義全体の概要、計算問題、文字列と言語	文字列と言語の概念を理解する
第2回	決定性有限オートマトン、形式的定義	決定性有限オートマトンの概念を理解する
第3回	非決定性計算、非決定性有限オートマトンと決定性有限オートマトンの等価性	非決定性計算の概念を理解する
第4回	有限オートマトンに関する演習	有限オートマトンの構成手法を理解する
第5回	正規演算、正規言語の閉包性、正規表現	正規表現の概念を理解する
第6回	正規表現と有限オートマトンの等価性	正規表現の性質を理解する
第7回	正規言語に対するポンピング補題	ポンピング補題の概念を理解する
第8回	文脈自由文法、文脈自由文法の曖昧さ	文脈自由文法の概念を理解する
第9回	正規言語に対するポンピング補題、および、文脈自由文法に関する演習	ポンピング補題の適用手法を理解する
第10回	Chomsky標準形	Chomsky標準形への変換手法を理解する
第11回	プッシュダウン・オートマトン、プッシュダウン・オートマトンと文脈自由文法の等価性 I	プッシュダウン・オートマトンの概念を理解する
第12回	プッシュダウン・オートマトンと文脈自由文法の等価性 II	等価性証明のための変換手法を理解する
第13回	文脈自由文法に対するポンピング補題	ポンピング補題の概念を理解する
第14回	文脈自由文法に対するポンピング補題に関する演習	ポンピング補題の適用手法を理解する

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

計算理論の基礎 (原著第 2 版) 1 オートマトンと言語, Michael Sipser 著, 太田和夫, 田中圭介監訳, 阿部正幸, 植田広樹, 藤岡淳, 渡辺治訳, 共立出版, 2008 年, ISBN 978-4320-12207-9. (原著: Introduction to the Theory of Computation, Second Edition, Michael Sipser, Thomson Course Technology, 2005, ISBN 978-0534-95097-2.)

参考書、講義資料等

初回の講義でお知らせします。

成績評価の方法及び基準

対面講義の場合: 授業中に行う小テスト60%と最終試験40%で評価を行います。
遠隔講義の場合: 授業中に行う小テストで評価を行います

履修の条件・注意事項

アルゴリズムとデータ構造の知識があることが望ましい。