例解図説オートマトンと形式言語入門

豊富な図と例で丁寧に説明しているから、初学者でもつまずきにくい。入門書に最適な、コンパクトな一冊。

『例解図説オートマトンと形式言語入門』 (岡留 剛 著、森北出版、2015 年 8 月刊) は、オートマトンと形式言語の理論を、有限状態オートマトンからチューリングマシンの停止問題まで全 7 章で解説する入門書です。大学図書館の書誌の内容説明には、豊富な図と例で丁寧に説明しているので初学者でもつまずきにくく、入門書に最適なコンパクトな一冊とあります。

有限状態オートマトンから停止問題までの全 7 章

目次は第 1 章「オートマトンと形式言語ことはじめ」で始まり、第 2 章「有限状態オートマトン」、第 3 章「文法」、第 4 章「プッシュダウンオートマトンと文脈自由文法」、第 5 章「チューリングマシン」、第 6 章「チョムスキーの階層」と進み、第 7 章「チューリングマシンの停止問題」で終わります。

第 2 章の有限状態オートマトンと第 4 章の文脈自由文法

オートマトンは、入力の記号を一つずつ読みながら内部の状態を切り替え、最後に受理か拒否かを答える抽象的な機械です。第 2 章の有限状態オートマトンは、Web アプリケーションの画面の遷移や通信プロトコルの手順を表す ステートマシン と同じ考え方で、この機械が受け付ける言語の範囲は 正規表現 で書ける範囲と一致します。第 4 章の文脈自由文法はプログラミング言語の構文の定義に使われ、コンパイラー の構文解析器はそれを読む仕組みです。

第 5 章のチューリングマシンと第 7 章の停止問題

第 5 章のチューリングマシンは、手順として書けるあらゆる計算を表すモデルです。第 6 章のチョムスキーの階層は、言語と文法を 4 つの型に分けた体系です。第 7 章が扱う停止問題は、任意のプログラムが止まるかどうかを判定する一般的な手順が存在しないという定理です。本書は、オートマトンと形式言語の基本の概念から計算可能性の限界までを、図と例を交えて全 7 章に収めています。