科目分野	理工学部
選必区分	選択
担当教員 ［ローマ字表記］	蓮沼　徹　[Toru Hasunuma]
授業形態	講義

授業の目的

　オートマトン理論，言語理論，計算論は計算機科学の理論的基盤であり重要な分野である。有限オートマトンの基本的事項，形式文法とオートマトンの関係，計算機（コンピュータ）の数学的モデルであるTuring機械を理解・応用できる能力を身につけることを目標とする。

授業概要

　オートマトン理論，言語理論，計算論についての基本的概念及び諸結果（決定性オートマトン，非決定性オートマトン，決定性と非決定性の等価性，正則表現，状態数最小化，形式文法，Turing機械）について講述する。また，適宜演習を設け演習問題を通じて理解を深めさせる。

到達目標

1. 有限オートマトンの基本的事項(決定性，非決定性，正則表現)，状態数最小化，文法とオートマトンの関係，Turing機械，判定不能性を理解する．

授業計画

第１回：基本的用語（アルファベット，文字列，言語）
第２回：決定性有限オートマトン（１）定義と例
第３回：決定性有限オートマトン（２）演習
第４回：正則言語の性質
第５回：非決定性有限オートマトン
第６回：決定性有限オートマトンと非決定性有限オートマトンの等価性
第７回：決定性有限オートマトンの状態数最小化（１）方法
第８回：決定性有限オートマトンの状態数最小化（２）演習
第９回：非正則言語
第１０回：正則表現（１）定義と例
第１１回：正則表現（２）正則表現とオートマトン
第１２回：形式文法とオートマトン
第１３回：Turing機械（１）定義と例
第１４回：Turing機械（２）演習
第１５回：Turing機械（３）認識不能性
定期試験

教科書

特になし

キーワード

オートマトン, 言語, 計算