オートマトン・言語理論の基礎 [単行本]

オートマトン・言語理論の基礎 [単行本] の 商品概要

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

  オートマトンは計算機のモデルであり、機械が計算するとはどのようなことか、機械は種類によって計算能力にどのような差があるか、機械の計算能力には限界があるのかなど、計算機科学の根底に潜む問いに答えるための道具である。一方、形式言語は日本語や英語などの自然言語やＣやＪａｖａなどのプログラミング言語のモデルである。文法によって言語が生成されるとはどのようなことか、言語とは何か、文法は種類によって言語の生成能力にどのような差があるのか、さらには文法の言語生成能力には限界があるのかなどの問いも計算機科学の重要な問題である。形式文法はこれらの問いに答えるための道具である。本書はオートマトン・言語理論の根本的な問いと課題に題材を絞り、丁寧に説明している。

• 目次

  第1章序論
  1.1　オートマトン･言語理論の内容
  1.1.1　　オートマトンとは
  1.1.2　　語とは何か,言語とは何か
  1.1.3　　形式文法とは
  1.1.4　　本書で学ぶ内容
  1.2　オートマトン･言語理論を学ぶための準備
  1.2.1　　集合の表し方
  1.2.2　　写像とは何か,写像の表し方
  【演習問題】
  第2章　有限オートマトン
  2.1　言語の識別機械としての有限オートマトン
  2.2　状態遷移図
  2.3　非決定性有限オートマトン
  2.4　空動作のある非法定性有限オートマトン
  2.5　L(dfa)=L(nfa)=L(ε-nfa)
  2.6　最簡形の決定性有限オートマトン
  2.7　有限オートマトンで識別できない言語
  【演習問題】
  第3章　プッシュダウンオートマトン
  3.1　決定性プッシュダウンオートマトン
  3.2　非決定性プッシュダウンオートマトン
  3.3　L(npda)⊃≠L(dpda)
  3.4　プッシュダウンオートマトンでは受理できない言語
  【演習問題】
  第4章　チューリング機械
  4.1　言語の識別機械としてのチューリング機械
  4.2　非決定性チューリング機械
  4.3　線形拘束オートマトン
  [話題4.1]　計算機械としてのチューリング機械
  [話題4.2]　2スタックオートマトン
  [話題4.3]　人間と有限オートマトン,人間とチューリング機械
  【演習問題】
  第5章　形式文法と形式言語
  5.1　言語の生成装置としての形式文法
  5.2　形式文法のクラスと形式言語のクラス
  5.3　正規文法と正規言語
  5.4　文脈自由文法と文脈自由言語
  5.5　文脈依存文法と文脈依存言語
  5.6　句構造文法と句構造言語
  【演習問題】
  第6章　オートマトンと形式文法の関係
  6.1　正規文法と有限オートマトン
  [話題6.1]　正規表現
  6.2　文脈自由文法とプッシュダウンオートマトン
  6.3　文脈依存文法と線形拘束オートマトン
  6.4　句構造文法とチューリング機械
  6.5　まとめと話題
  [話題6.2]　文法の標準形
  【演習問題】
  第7章　言語の階層構造
  7.1　正規言語の性質と正規言語ではない言語の存在
  7.2　文脈自由言語の性質と文脈自由言語ではない言語の存在
  [話題7.1]　 あいまいな言語について
  7.3　文脈依存言語の性質と文脈依存言語ではない言語の存在
  7.4　句構造言語の性質と句構造言語ではない言語の存在
  【演習問題】
  解答
  参考文献

• 内容紹介

  本書は大学や短大あるいは高専における授業のテキストとして書かれている｡
  オートマトン･言語理論が扱う題材は多岐にわたるが、本書では思い切って根本的な問いと課題に題材を絞り、その分丁寧にわかりやすく説明することとした｡これらの問いと課題に答えていく中で、計算機科学あるいは情報工学の基礎としてのオートマトン理論並びに形式言語理論の持つ考え方が理解でき、その美しさと面白さを十分に味わうことができるからである｡
  
  本書が扱うのは理論であるが、本文中に証明は一切ない｡わかりやすさのために厳密さを犠牲にした訳ではない｡考え方を理解するのに必要なのは多数の例とわかりやすい説明とをもとに学生･生徒諸君が自分で考えることであり、証明は不要だからである｡
  大学や短大･高専で学ぶ1人でも多くの人がオートマトン･言語理論の基礎を理解し、モデルを用いて推論することの美しさと面白さを体得することによって、ますます進展する高度情報化社会で伸びていくための素養を身につけていただきたい｡本書が少しでもその役に立てば幸いである｡

• 著者紹介（「BOOK著者紹介情報」より）（本データはこの書籍が刊行された当時に掲載されていたものです）

  米田 政明(ヨネダ マサアキ)
  １９７２年東北大学大学院工学研究科修了。現在、富山大学工学部教授
  
  広瀬 貞樹(ヒロセ サダキ)
  １９８０年東北大学大学院工学研究科修了。現在、富山大学工学部教授
  
  大里 延康(オオサト ノブヤス)
  １９７６年東北大学大学院工学研究科修了。現在、大阪工業大学情報科学部教授
  
  大川 知(オオカワ サトシ)
  １９７９年東北大学大学院工学研究科修了。現在、会津大学コンピュータ理工学部教授

オートマトン・言語理論の基礎 [単行本] の商品スペック