科目名 : 言語・オートマトン

科目コード 91040
配当学年 2年
開講期 後期
曜時限 水曜・1時限
講義室 総合研究7号館情報1
単位数 2
履修者制限
講義形態 講義
言語
担当教員 岩間一雄

講義概要

有限オートマトンについて述べ、さらに文脈自由言語や チューリング機械等、オートマトンと言語理論について講述する。また、これらの応用についても適宜言及する。

評価方法

2回のレポートと最終試験の結果による.

最終目標

講義計画

項目 回数 内容説明
有限オートマトン 5 オートマトンの表現、最小化、正則表現と文法
文脈自由言語 4 プッシュダウンオートマトン、文脈自由文法、等価性
チューリング機械および関連する話題 4 チューリング機械の定義、万能性、チューリング機械と等価な機械、文脈依存文法、言語の演算
言語の能力差 2 最後に言語階層全体のまとめを行う。講義の最後に学習到達度判定のための質疑を行う.

教科書

岩間,オートマトン・言語と計算理論,コロナ社,2003

参考書

予備知識

授業URL

その他