形式言語とオートマトン

今日の計算機の基礎的なモデルとなったオートマトンと、それと対をなす形式言語理論について学ぶ。情報工学の基礎をなす科目であり、ソフトウェア作成においても重要なものである。形式言語理論はプログラミング言語の構造や解析の基礎となるものである。有限オートマトンについては、正規表現、決定性、非決定性、ε動作、最小化などについて述べる。更に文脈自由言語、プッシュダウンオートマトン、正規表現コマンド、セルオートマトンなどについて述べる。本科目はコンパイラ、プログラミング、アルゴリズムとデータ構造などの基礎をなすものである。

達成目標

1.	BNF記法、逆ポーランド記法 (授業計画の1〜４に対応)
2.	正規方程式の解法 (授業計画の５〜７に対応)
3.	NFAのDFAへの変形 (授業計画の９に対応)
4.	ε-NFAのNFAへの変形 (授業計画の1０に対応)
5.	DAFの最小化操作 (授業計画の1１〜１４に対応)

授業計画

1.	数学的準備　　・集合、再帰的構造、チョムスキの４階層
2.	形式言語と帰納的表現　　・語、言語、クリーネ閉包、スター演算
3.	ＢＮＦ記法　　・メタ言語、構文図式：小テスト
4.	離散グラフ　　・ポーランド、逆ポーランド記法
5.	言語と文法　　・オートマトンの階層、ミーリ機械、ムーア機械
6.	正規言語（１）　　・言語の受理、決定性オートマトン（DFA）
7.	正規言語（２）　　・正規表現、正規方程式：小テスト
8.	中間テスト
9.	有限オートマトン（１）　　・非決定性オートマトン（NFA）、DFA化：小テスト
10.	有限オートマトン（２）　　・εNFA、NFA化：小テスト
11.	有限オートマトン（３）　　・DFAへの変換
12.	有限オートマトン（４）　　・Myhill-Nerodeの定理、同値類
13.	有限オートマトン（５）　　・最小化
14.	有限オートマトン（６）　　・最小化演習：小テスト
15.	テスト

開講部	工学部
開講学科	情報工学科
開講学年	1年次
開講時期	後期
単位数	2
単位区分	選択
系列区分	専門
講義区分	講義

L0920400

授業の概要

達成目標

授業計画

評価方法と基準

教科書・参考書

履修前の準備

オフィスアワー

環境との関連