言語理論とオートマトン：シラバス

■ 講座情報

　　言語理論とオートマトン

【主任講師】

　　山﨑　秀記（放送大学客員教授）

【教材・資料】

　　言語理論とオートマトン 　　（山崎の講義資料）

• オートマトン　言語理論　計算論　I　[第2版]
  　　（ホップクロフト、モトワニ、ウルマン／サイエンス社／\3,024／ISBN=9784781910260）
• オートマトン　言語理論　計算論　II　[第2版]
  　　（ホップクロフト、モトワニ、ウルマン／サイエンス社／\2,808／ISBN=9784781910277）

---

【授業内容】

　　この授業でいう言語とは、文（文字列）の集りです。
　　言語を生成する仕組みとしての文法と、
　　言語を認識する仕組みとしてのオートマトン（自動機械）との
　　対応関係について学びます。
　　この分野は、
　　コンピュータによるテキスト処理や構文解析など幅広い応用を持ち、
　　さらには計算機の能力の限界を明らかにする、
　　計算機科学の重要な基礎分野です。
　　初修者には全体的な地図の、
　　経験者には知識の整理に役立つ諸概念の理解を目的として、
　　できるだけ分かりやすく解説します。

【授業テーマ】

• 第1回講義概要、言語とは
• 第2回正規言語
• 第3回正規言語の応用
• 第4回文脈自由言語
• 第5回文脈自由言語の応用
• 第6回帰納的可算言語
• 第7回計算可能性
• 第8回計算量の理論

以上