Course's Home Page


53060

形式言語

Theory of Automata and Formal Languages


担当教官:B.H. Far (工学部 助教授)
学科専門科目 指定選択科目 2単位
対象学科:情報
学年学期:2年・後期
時間割 :木3・4
教室  :41
受講に必要な既修科目:プログラミング言語を履修していることが望ましい
過年度生の他学科開講の同一名科目の受講:可

概要

オートマトン及び形式言語理論は、計算機科学の基礎の重要な理論であり、 その応用も極めて広い。本講義では、次の基礎概念についてその理解を深める。
順序機械, 有限オートマトン, 正則表現, 正則文法, 文脈自由文法, プッシュダウンオートマトン, チューリングマシン。
また、 講義資料 オンライン自動採点演習 が用意されてますので遠隔授業を受けることがで きます。


1. 序論
位置付け, 数学的準備

2. 順序機械
順序機械の紹介
状態遷移図と状態遷移表
ミーリー型順序機械 (Mealy machine)
ムーア型順序機械 (Moore machine)
ミーリー型からムーア型への変換
ムーア型からミーリー型への変換
順序機械の簡単化

3. 有限オートマトン (その1)
有限状態オートマトン:FSA
決定性有限オートマトン:DFA
正則言語:RL
到達性・等価性

4. 有限オートマトン (その2)
有限オートマトンの最簡形
ハフマン・ミーリーの簡単化法
非決定性有限オートマトン:NFA
非決定性有限オートマトンの状態推移
非決定性有限オートマトンによる受理

5. 有限オートマトン (その3)
NFAからDFAへの変換:部分集合構成法
ε-動作をもつ非決定性有限オートマトン
ε-動作をもつ非決定性有限オートマトンの状態推移
ε-動作をもつ非決定性有限オートマトンによる受理
ε-動作の除去

6. 正則表現
言語演算:連接
言語演算:スタークロージャ
正則集合
正則表現
有限オートマトンから正則表現へ変換
正則表現から有限オートマトンへ変換
非正則言語

7. 形式文法
形式文法:FG (Formal Grammar)
正則文法:RG (Regular Grammar)
正則文法から有限オートマトンへの変更
有限オートマトンから正則文法への変更

8. 文脈自由文法・言語(CFG/CFL)
導出木(Derivation Tree)
文脈自由文法の簡単化:無効記号
文脈自由文法の簡単化:ε-生成規則
文脈自由文法の簡単化:単位生成規則
文脈自由文法の標準形:チョムスキ標準形
文脈自由文法の標準形:グライバッハ標準形

9. 演習

10. プッシュダウンオートマトン (その1)
単純決定性文法
【復習】決定性有限オートマトン
プッシュダウンスタック
単純決定性プッシュダウンオートマトン
単純決定性言語

11. プッシュダウンオートマトン(その2)
【復習】単純決定性プッシュダウンオートマトン
決定性プッシュダウンオートマトン−1
決定性プッシュダウンオートマトン−2
推移ルール δ について
動作と受理概念
非決定性プッシュダウンオートマトン
非決定性プッシュダウンオートマトンから文脈自由文法への変更

12. チューリングマシン - (1)
【復習】正則文法(3型)と文脈自由文法(2型)
句構造文法(0型文法)
文脈依存文法(1型文法)
【復習】決定性プッシュダウンオートマトン
チューリング機械

13. チューリングマシン(その2)
計算可能性
計算量、NP完全性

14. テスト
自動採点テスト:その1
自動採点テスト:その2

■ 教科書:富田悦次、横森貴、”オートマトン・言語理論” 森北出版
■ 参考書:小倉久和、”言語理論と有限オートマトン入門” コロナ社
■ 参考書:J.ホップクロフト、J.ウルマン、(野崎 他訳)
      ”オートマトン 言語理論 計算論 I” サイエンス社

■ 成績の評価方法:○期末試験40%    ○出席点+レポート60%
■ 授業の形式:通常の授業

担当教官電話:(dial-in) 858-9612
E-Mail:far@cit.ics.saitama-u.ac.jp

担当教官のホームページ