形式言語・オートマトン入門

書影

グラフィック情報工学ライブラリ  3

形式言語・オートマトン入門

定価:
1,980
(本体:1,800円+税)
難易度:入門

発行日:2017年8月25日

発行:数理工学社

ISBN:978-4-86481-047-0

サイズ:並製A5

ページ数:176ページ

在庫:在庫あり

内容詳細

計算機の基礎となる形式言語と形式文法,オートマトンについて,情報系学部生向けに分かりやすく解説した入門書.例や例題を多数交え,見開き構成で平易に記した好個の書.最終章では木文法と木オートマトンについて紹介した.

目次

第1章 形式言語と形式文法
  1.1 なぜ文法が必要なのか
  1.2 言語,文法の形式的な定義
  1.3 文法の例
  1.4 チョムスキー階層
  1.5 空列を生成するためのε-規則の導入
  演習問題

第2章 有限オートマトン
  2.1 有限オートマトンとは
  2.2 有限オートマトンの例
  2.3 状態遷移関数の緩和
  2.4 有限オートマトンの状態遷移表による表現
  2.5 非決定性有限オートマトン
  2.6 非決定性有限オートマトンの例
  2.7 非決定性有限オートマトンと決定性有限オートマトンの能力
  2.8 有限オートマトンと正規文法
  2.9 ε-動作を許した非決定性有限オートマトン
  2.10 状態数が最小の決定性有限オートマトン
  演習問題

第3章 正規表現と正規言語
  3.1 正規表現とは
  3.2 形式言語における正規表現
  3.3 正規表現の簡略化
  3.4 正規表現と有限オートマトン
  3.5 正規言語の性質
  3.6 正規言語の所属性判定と等価性判定
  3.7 正規言語のクラスに含まれない言語
  演習問題

第4章 文脈自由文法
  4.1 文脈自由文法と構文木
  4.2 最左導出と最右導出と文法のあいまい性
  4.3 文脈自由文法の標準形
  4.4 チョムスキー標準形に変換する方法
  4.5 グライバッハ標準形に変換する方法
  4.6 文脈自由文法の構文解析
  4.7 文脈自由文法に関する判定問題
  4.8 文脈自由文法では生成することができない言語
  演習問題

第5章 プッシュダウンオートマトン
  5.1 プッシュダウンオートマトンとは
  5.2 プッシュダウンオートマトンの例
  5.3 受理状態による受理と空スタックによる受理
  5.4 プッシュダウンオートマトンと文脈自由文法
  5.5 決定性プッシュダウンオートマトン
  演習問題

第6章 木文法と木オートマトン
  6.1 木文法を考える意味
  6.2 ML文脈自由木文法
  6.3 正規木文法
  6.4 有限木オートマトン
  演習問題

演習問題解答
索引

サポート情報

正誤表

関連書籍

コンピュータと表現

平川正人

1,760円(税込)

入門
論理回路入門

菅原一孔

1,760円(税込)

入門