ダウンロード 例解図説 オートマトンと形式言語入門 mobi 本

オートマトンや形式言語の概念を直観的に理解できるように配慮した,コンパクトなテキストです. 図や例を豊富に用いるとともに,理解を深めるのに重要な定理については例を用いて証明の流れを説明していますので,難解になりがちな数学的内容をつまずくことなく学べます. つまずきやすい点を意識して説明を補っていますので,初めて学ぶ読者におすすめの一冊です. &lt【;目次】第1章 オートマトンと形式言語ことはじめ 1.1 オートマトンと形式言語を学ぶ意義 1.2 オートマトンと形式言語とは 1.3 オートマトン(状態機械/形式言語) 1.4 数学的準備 1.5 写像 1.6 数学的帰納法と背理法 1.7 形式言語理論の用語 第2章 有限状態オートマトン 2.1 決定性有限状態オートマトンと受理言語(決定性有限状態オートマトン/決定性有限状態オートマトンの受理言語) 2.2 非決定性有限状態オートマトンと受理言語(非決定性有限状態オートマトン/非決定性有限状態オートマトンの受理言語/DFAとNFAの言語受理能力) 2.3 空動作のある非決定性有限状態オートマトン 2.4 正規表現 2.5 状態数最小のオートマトン(状態数最小の決定性有限状態オートマトン/状態数最小のDFA のつくり方:方針/関係・同値関係・同値類/Σ∗ 上の同値関係/Minimum DFAの正当性) 2.6 ポンプの補題 第3章 文法 3.1 文法と言語(形式文法/語(文)の導出と言語) 3.2 正規文法と正規言語 第4章 プッシュダウンオートマトンと文脈自由文法 4.1 プッシュダウンオートマトン 4.2 決定性プッシュダウンオートマトンと受理言語(決定性プッシュダウンオートマトン/決定性プッシュダウンオートマトンの動作と受理言語) 4.3 非決定性プッシュダウンオートマトンと受理言語 4.4 文脈自由文法 4.5 文脈自由文法の簡素化と標準形(文法の簡素化/文脈自由文法の標準形) 4.6 構文解析(下降型構文解析(トップダウン型構文解析)/上昇型構文解析(ボトムアップ型構文解析)/文法のあいまいさ) 4.7 文脈自由文法とプッシュダウンオートマトン(プッシュダウンオートマトンの受理言語3種/非決定性プッシュダウンオートマトンと文脈自由言語の等価性) 4.8 文脈自由言語に対するポンプの補題 付記 第5章 チューリングマシン 5.1 チューリングマシン 5.2 線形拘束オートマトン 付記 第6章 チョムスキーの階層 6.1 文脈依存文法と文脈依存言語 6.2 句構造文法と句構造言語 6.3 チョムスキーの階層 6.4 言語クラスの閉包性 第7章 チューリングマシンの停止問題 7.1 無限を数える(無限の「数え方」: 1対1対応/カントールの対角線論法) 7.2 チューリングマシンの停止問題 付記 参考文献 演習問題解答例 索引