形式言語と有限オートマトン入門 - 例題を中心とした情報の離散数学 -

形式言語と有限オートマトン入門 - 例題を中心とした情報の離散数学 -

記号処理はコンピュータの基本的な機能である。本書は,記号処理の基本である形式言語とオートマトンの基礎的な概念について,例題を多数挙げ解説する形式で系統的に記述した。

ジャンル
発行年月日
1996/10/15
判型
A5
ページ数
234ページ
ISBN
978-4-339-02339-8
形式言語と有限オートマトン入門 - 例題を中心とした情報の離散数学 -
在庫あり
2営業日以内に出荷致します。

定価

3,080(本体2,800円+税)

カートに入れる

購入案内

  • 内容紹介
  • 目次
  • 著者紹介

記号処理はコンピュータの基本的な機能である。本書は,記号処理の基本である形式言語とオートマトンの基礎的な概念について,例題を多数挙げ解説する形式で系統的に記述した。

1 数学的準備
1.1 集合と写像
  1.1.1 集合
  1.1.2 関係
  1.1.3 写像
1.2 代数系
  1.2.1 演算と代数系
  1.2.2 順序集合と束,ブール代数
1.3 記号論理
  1.3.1 命題論理
  1.3.2 述語論理
2 帰納的表現と形式言語
2.1 数学的帰納法
  2.1.1 自然数と無限
  2.1.2 数学的帰納法
2.2 帰納的記述
  2.2.1 帰納的定義
  2.2.2 再帰的構造と再帰的アルゴリズム
2.3 形式言語と帰納的表現
  2.3.1 形式言語
  2.3.2 形式言語の性質
  2.3.3 形式言語としての数式
  2.3.4 形式言語の表現
3 離散グラフと木グラフ
3.1 離散グラフ
  3.1.1 有限グラフとグラフの表現
  3.1.2 完全グラフ,正則グラフ,2部グラフ,木グラフ
  3.1.3 多重グラフと有向グラフ
3.2 グラフ理論
  3.2.1 グラフの性質
  3.2.2 グラフの行列表現
  3.2.3 関係の有向グラフ表現
  3.2.4 オイラーグラフとハミルトングラフ
3.3 木グラフ
  3.3.1 木の特徴
  3.3.2 グラフの探索と探索木
  3.3.3 順序木
  3.3.4 数式の構文と構文解析
4 有限オートマトンと正規表現
4.1 順序機械と有限状態機械
  4.1.1 順序機械とフリップフロップ
  4.1.2 簡単な順序機械
4.2 有限オートマトン
  4.2.1 有限オートマトン
  4.2.2 有限オートマトンと言語の認識
4.3 正規表現
  4.3.1 正規表現の定義と性質
  4.3.2 有限オートマトンの受理する言語の正規表現
4.4 DFAと正規表現の同等性およびDFAの最小化
  4.4.1 非決定性有限オートマトン
  4.4.2 非決定性FAの決定性FAへの変換
  4.4.3 ε-動作を含むNFA
  4.4.4 正規表現で表された言語を受理するε-NFA
  4.4.5 Myhill-Nerodeの定理と有限オートマトンの最小化
  4.4.6 有限オートマトンの応用
4.5 プッシュダウンオートマトンとチューリング機械
  4.5.1 プッシュダウンオートマトン
  4.5.2 チューリング機械
  4.5.3 オートマトンと計算理論
5 形式言語理論入門
5.1 形式言語理論
  5.1.1 形式文法
  5.1.2 文の生成と導出
5.2 文脈自由文法
  5.2.1 プロダクションの文脈自由性と文脈依存性
  5.2.2 文脈自由文法と導出木
  5.2.3 文脈自由文法の簡単化
  5.2.4 文脈自由文法の標準形
5.3 線形文法と正規言語
  5.3.1 線形文法とNFA
  5.3.2 正規文法と正規表現
5.4 形式言語のクラス階層とオートマトン
5.5 言語処理への応用
  5.5.1 簡単なプログラム言語の定義
  5.5.2 パーザ
  5.5.3 プログラミング言語
  5.5.4 Prologによる自然言語処理
参考文献
例題の略解
索引

小倉 久和(オグラ ヒサカズ)