◇ 担当教員：伊藤　実（いとう　みのる）　安本　慶一（やすもと　けいいち）

◇ 担当教員：	伊藤　実（いとう　みのる）
◇ 単位数：１ ◇選択･必修：選択 ◇開講時期：�U期 月曜１限 ◇講義室：L2

◇ 授業目的：
形式言語理論、オートマトン理論の基礎的な知識は、情報科学分野において必須と言える素養である。
本講義では、構文解析や言語処理の元になる概念である文脈自由言語に関する基本的な事柄を理解す
ることを目的とする。

◇ 授業内容：
ソースプログラムからオブジェクトに変換するソフトウェアであるコンパイラの基本的な処理として
、語彙解析と構文解析がある。語彙解析は正則文法に、また、構文解析は文脈自由文法にそれぞれ密
接に関連している。さらに、文脈自由言語は、自然言語の最も素朴なモデルと考えられる。
本講義では、まず文脈自由言語を定義するために文脈自由文法を導入し、対応する機械であるプッシ
ュダウンオートマトンを説明する。それらの等価性を証明した後、チョムスキー標準形を導入し、パ
ンピングレンマを証明する。パンピングレンマを用いて、非文脈自由言語の存在を具体的に示す。時
間に余裕があれば、決定性文脈自由言語を紹介する。
具体的な項目として、次の順に学んでいく。
１．文脈自由言語、文脈自由文法の定義 
２．プッシュダウンオートマトンの定義
３．文脈自由文法とプッシュダウンオートマトンの等価性
４．チョムスキー標準形 
５．パンピングレンマと非文脈自由言語
６．決定性文脈自由言語
　概念の理解を助けるため、授業中に、適宜簡単な演習問題を解かせる。

◇ 教科書　：
エフィーム・キンバー、カール・スミス著、筧・杉原訳 ： 計算論への入門、ピアソン・エデュケーション、2002
◇ 参考書　：
１．J.E.Hopcroft, R.Motwani and J.D.Ullman: Introduction to Automata Theory, Languages,
 and Computation second edition, Addison-Wesley, 2000
２．富田悦次・横森貴著：オートマトン・言語理論、森北出版 
３．岩間一雄：アルゴリズム理論入門、昭晃堂、2001
◇ 履修条件：
必須条件ではないが、計算理論Iを履修していることを前提とする。履修希望者は、1回目または２回目の
授業時間に履修登録する。
◇ 成績評価：
試験（100％）により評価する。
◇ オフィスアワー：
（A611）月曜日５限。その他、e-mailにて相談の上随時。