形式言語の理論
著者名 有川 節夫 監修
西野 哲朗
石坂 裕毅
稲垣 康善 編集委員
土居 範久 編集委員
発行元 丸善出版
発行年月日 2009年10月
判型 A5 210×148
ページ数 222ページ
ISBN 978-4-621-08209-6
Cコード 3355
NDCコード 007
ジャンル 電気・電子・情報工学

内容紹介

形式言語理論で伝統的に扱われる主要な題材は網羅した上で、論理プログラムの理論と言語理論の関連等、最近の新しい研究展開の成果を取り込んだ、大学の情報科学系学科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 自然言語の複雑さ

関連商品

定価:3,850円
(本体3,500円+税10%)
在庫:品切れ・重版未定