情報情報科学・基礎標準
オートマトン・言語理論(第2版・新装版)
有限オートマトンからチューリング機械まで、形式言語との対応を学ぶ。正規言語と有限オートマトン、文脈自由文法、チューリング機械、計算可能性などを扱う、標準レベルの教科書です。院試での使い方も解説します。
![]()
- 書名
- オートマトン・言語理論(第2版・新装版)
- 著者
- 富田悦次・横森貴(共著)
- 出版社
- 森北出版
- 発行
- 2023-10
- 分野
- 情報/情報科学・基礎
※当ページのリンクには広告が含まれています。
多くの大学で使われてきた、オートマトンと言語理論の教科書です。256ページ・全6章で、有限オートマトンと正規表現、言語と形式文法、文脈自由文法とプッシュダウンオートマトン、句構造文法とチューリング機械、決定問題を扱います。
自動販売機や英文法といった身近な例から入り、少しずつ一般的な議論へと進みます。オートマトンと言語の対応関係を、丁寧に解き明かしているのが特色です。
- 院試で、オートマトンや形式言語が出題される人
- 計算理論の基礎を、例から順に学びたい人
集合と論理の基本的な記法を知っていれば取り組めます。
- 第1章 序論
- 第2章 有限オートマトンと正規表現
- 第3章 言語と形式文法
- 第4章 文脈自由文法とプッシュダウンオートマトン
- 第5章 句構造文法とチューリング機械
- 第6章 決定問題
抽象的な定義の前に、具体的な例を示しています。定理の証明が丁寧で、構成の手順を追うことができます。
院試で出題が最も多いのは、第2章「有限オートマトンと正規表現」です。決定性と非決定性のオートマトンの変換、状態数の最小化、正規表現との相互の変換は、手順を覚えて、手を動かして練習してください。与えられた言語が正規言語でないことを示す問題も、定番です。
次に重要なのは、第4章「文脈自由文法とプッシュダウンオートマトン」です。与えられた言語を生成する文法を作る問題、導出木を描く問題、文法があいまいかどうかを判定する問題が出ます。
第3章「言語と形式文法」では、文法の4つの階層と、それぞれに対応するオートマトンを整理します。
第5章のチューリング機械と、第6章「決定問題」は、計算可能性を扱います。出題する志望先とそうでない志望先が分かれるため、過去問に出ていなければ、概要をつかむ程度で構いません。
次の問いに答えられるかを確かめてください。
- 正規表現から、対応する有限オートマトンを作れるか
- ある言語が正規言語でないことを、反復に関する補題で示せるか
- 簡単な言語について、文脈自由文法を書けるか
理論的な内容で、証明が多く含まれます。計算量理論(PやNPなどのクラス)は、中心的な話題ではないため、出題される場合は別の本で補ってください。
読み終えたら、志望先の過去問で、変換と構成の問題を繰り返し解きます。
オートマトン・言語理論(第2版・新装版)
新・明解C言語で学ぶアルゴリズムとデータ構造第2版標準・参考書キタミ式イラストIT塾 応用情報技術者 令和08年技術評論社
キタミ式イラストIT塾 応用情報技術者 令和08年標準・資格試験対策書問題解決力を鍛える!アルゴリズムとデータ構造講談社
問題解決力を鍛える!アルゴリズムとデータ構造標準・教科書期間限定!入会金無料キャンペーン!
11月30日までのお申し込みで、
入会金30,000円が無料!
また、ご満足いただけない場合は安心の全額返金保証制度あり!
無料体験講義のお申し込み
下記に必要事項を記入の上、【送信】を押してください。
数日以内に担当のものからメールでお返事させていただきます。
※迷惑メール設定を解除いただくようお願いいたします。
院試塾INPASSのサービス内容は、こちらからご確認いただけます。
INPASSの詳細を見る情報の最終確認日:2026-11-17
