オートマトン

オートマトンとは現在使われているコンピュータを含む様々な計算機構の数理モデルである. チューリング機械に代表される1次元テープオートマトンが有名であるが, グラフオートマトンやセルオートマトンなど多種類が考案されている. この講義では決定性/非決定性有限オートマトンの概念を紹介し, 計算理論との関係について説明する. また, オートマトンは言語を受理する抽象的な機械といえる. オートマトンと対をなす形式言語についても触れ, コンパイラやプログラミングの基礎となる理論について学べるようにする.

達成目標

授業計画

	【授業計画】	【授業時間外課題（予習および復習を含む）】
1.	数学的準備 1 (集合/関数と関係)	集合論について復習.
2.	数学的準備 2 (グラフ/文字列と言語)	グラフ, 言語について予習.
3.	決定性有限オートマトン (DFA)	前回のノート・資料の復習. 資料の今回授業予定部分を読んで予習 (以下同様; ポイントのみ記述).
4.	正規言語 (RL)	文字列と言語, DFAの定義の確認.
5.	非決定性有限オートマトン (NFA)	正規言語, 正規演算の確認.
6.	DFA と NFA の等価性	DFA と NFA の定義の確認.
7.	正規表現 (REX) と正規言語	文字列と言語, 正規演算の再確認.
8.	正規表現と正規言語の等価性, 正規言語の例	正規表現, 正規言語の確認.
9.	正規言語に関するポンピング補題と非正規言語	正規言語と NFA の関係を確認.
10.	文脈自由文法（CFG）と文脈自由言語 (CFL)	非正規言語について確認.
11.	文法の曖昧さとチョムスキー標準形	言語の生成について確認.
12.	プッシュダウンオートマトン（PDA）	CFG/CFL について確認.
13.	CFG と PDA の等価性	CFG/CFL, および, PDA の確認.
14.	文脈自由言語に関するポンピング補題と非文脈自由言語	CFG/CFL, および, CFL に関するポンピング補題の確認.
15.	期末試験とその講評	全体の復習.

評価方法と基準

教科書・参考書

適宜プリントを配布する. 参考書として「計算論への入門」, エフィーム・キンバー他, ピアソン・エデュケーション, 「計算理論の基礎2 計算可能性の理論」, 「同3 複雑さの理論」, いずれもMichael Sipser, 共立出版, をあげておく.

開講部	システム理工学部
開講学科	数理科学科
開講学年	2年次
開講時期	後期
単位数	2
単位区分	選択
系列区分	専門
講義区分	講義

V0530000

授業の概要

達成目標

授業計画

評価方法と基準

教科書・参考書

履修登録前の準備

環境との関連

地域志向

社会的・職業的自立力の育成

アクティブ・ラーニング科目

1.	決定性と非決定性の有限オートマトンの違いと言語認識の意味での等価性を理解する.
2.	オートマトンと言語の関係について理解する.
3.	言語のクラスにおける階層構造について理解する.