内容紹介
形式言語理論で伝統的に扱われる主要な題材は網羅した上で、論理プログラムの理論と言語理論の関連等、最近の新しい研究展開の成果を取り込んだ、大学の情報科学系学科3〜4年生および大学院生のテキスト。
目次
1 準備
1.1 アルファベット,記号,言語
1.2 句構造文法
1.3 関係,関数,術語
1.4 グラフと木
2 計算可能性と計算量
2.1 アルゴリズム
2.2 Turing機械
2.3 計算可能性
2.4 計算量
2.5 NP完全性
2.6 問題
3 正則言語
3.1 有限オートマトン
3.2 非決定有限オートマトン
3.3 正則言語の性質
3.4 Nerodeの定理
3.5 DFAの状態最小化
3.6 その他の表現型
3.7 問題
4 文脈自由言語
4.1 文脈自由文法
4.2 文法自由文法の導出木
4.3 文脈自由文法の標準形
4.4 プッシュダウン・オートマトン
4.5 閉包性
4.6 Cocke-Kasami-Youngerアルゴリズム
4.7 問題
5 文脈依存言語
5.1 文脈依存文法とその標準形
5.2 線形有界オートマトン
5.3 文脈依存言語の性質
5.4 言語族の性質
5.5 問題
6 EFS
6.1 EFSとEFS言語
6.2 EFSの部分クラス
6.3 融合原理による言語の受理
6.4 EFS言語族とChomsky階層
6.5 EFSに関する最近の話題
6.6 問題
7 自然言語構文論における形式的手法
7.1 自然言語の生成系と認識系
7.2 拡張遷移ネットワーク
7.3 上昇型語彙機能文法
7.4 自然言語の複雑さ