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

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

• 要旨（「BOOK」データベースより）

  本書は大学低学年の理工系の学生を対象としているが、内容を選択的に利用すれば、高専を含めて非専門の学科や学部、あるいは文系の学部でも利用できると考えている。第１章は予備的な章として、論理的な記述とその理解を助けるため、必要な用語と記号について簡単に説明した。第２章は、離散数学の論理的な記述に欠かせない帰納法と、形式言語の導入的な部分をまとめた。第３章は、視覚的な表現としてきわめて広範に用いられている離散グラフについて、基礎的な部分をまとめた。後半は木グラフを中心に、形式言語との関係も示した。第４章は、有限オートマトンについて、入門的な事項を中心にまとめた。第５章は、文脈自由文法と正規文法を中心に、形式言語の理論について解説した。

• 目次

  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による自然言語処理
  
  参考文献
  例題の略解
  索引

• 内容紹介

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

形式言語と有限オートマトン入門―例題を中心とした情報の離散数学 の商品スペック