講義名 オートマトンと言語 　(Automata and Formal Languages)
開講学期 4 学期 単位数 2--1--0
担当教員 （Eクラス）：篠田 浩一 助教授　　西8棟(E) 4階 402号室　　内線：3526
（Oクラス）：松本 隆太郎 助教授　　南3号館 3階 311号室 内線：3864
講義の目的 プログラム言語処理と自然言語処理の基礎となる形式言語について，生成する手段と 認識する機械の二つの観点から講義する．
知識
ユニット
  • オートマトン（有限オートマトン，プッシュダウン・オートマトン）
  • 句構造文法（正規文法，文脈自由文法）
  • 正規表現
  • オートマトンや形式言語に関するアルゴリズム
関連科目・
履修条件等		 <--- 　 計算基礎論
---> 　 コンパイラ構成， 自然言語処理論（大学院）
教科書
  • コンピュータサイエンスのための言語理論入門，R. Smith 著，吉田 敬一 他訳， 共立出版，1986，2300 円
参考書
  • オートマトン，言語理論，計算論Ｉ[第2版](Introduction to Automata Theory, Languages, and Computation Second Edition) J. Hopcroft, R. Motowani, J. Ullman 著，野崎 昭弘， 高橋 正子，町田 元，山崎 秀記 訳，サイエンス社，2002, 2800円
講義計画
  1. 言語の研究方法，句構造文法，正規表現とその言語
  2. 有限オートマトンとその受理言語
  3. 有限オートマトンと正規表現の等価性
  4. 決定性有限オートマトンの状態数最小化
  5. 正規文法と正規言語，正規文法と正規表現の等価性
  6. 正規言語の特徴付け，非正規言語の例と証明
  7. 中間試験
  8. 文脈自由文法と文脈自由言語
  9. プッシュダウン・オートマトンとその受理言語
  10. 文脈自由文法の標準形
  11. 文脈自由言語の特徴付け
  12. 非文脈自由言語の例と証明，閉包性
  13. プログラム言語の構文の非文脈自由性，決定性文脈自由言語の性質
  14. 文脈自由言語の認識アルゴリズム
  15. 言語の階層
成績評価 出席状況，中間試験，期末試験により評価する．
試験問題・
略解の公開 		試験問題は直接配布、略解は直接配布またはWebにて公開
担当教員
からの一言 		特になし
関連サイト


インデックスへ戻る