オートマトン・言語理論(第2版・新装版)

オートマトン・言語理論(第2版・新装版)

情報情報科学・基礎標準

オートマトン・言語理論(第2版・新装版)

有限オートマトンからチューリング機械まで、形式言語との対応を学ぶ。正規言語と有限オートマトン、文脈自由文法、チューリング機械、計算可能性などを扱う、標準レベルの教科書です。院試での使い方も解説します。

レベル標準
種別教科書
学習期間の目安約1か月
ページ数256ページ
定価(参考)3,080円
書名
オートマトン・言語理論(第2版・新装版)
著者
富田悦次・横森貴(共著)
出版社
森北出版
発行
2023-10
分野
情報/情報科学・基礎

※当ページのリンクには広告が含まれています。

どんな参考書か

多くの大学で使われてきた、オートマトンと言語理論の教科書です。256ページ・全6章で、有限オートマトンと正規表現、言語と形式文法、文脈自由文法とプッシュダウンオートマトン、句構造文法とチューリング機械、決定問題を扱います。

自動販売機や英文法といった身近な例から入り、少しずつ一般的な議論へと進みます。オートマトンと言語の対応関係を、丁寧に解き明かしているのが特色です。

向いている人
  • 院試で、オートマトンや形式言語が出題される人
  • 計算理論の基礎を、例から順に学びたい人
前提知識

集合と論理の基本的な記法を知っていれば取り組めます。

収録内容と特徴
  • 第1章 序論
  • 第2章 有限オートマトンと正規表現
  • 第3章 言語と形式文法
  • 第4章 文脈自由文法とプッシュダウンオートマトン
  • 第5章 句構造文法とチューリング機械
  • 第6章 決定問題

抽象的な定義の前に、具体的な例を示しています。定理の証明が丁寧で、構成の手順を追うことができます。

院試対策での使い方

院試で出題が最も多いのは、第2章「有限オートマトンと正規表現」です。決定性と非決定性のオートマトンの変換、状態数の最小化、正規表現との相互の変換は、手順を覚えて、手を動かして練習してください。与えられた言語が正規言語でないことを示す問題も、定番です。

次に重要なのは、第4章「文脈自由文法とプッシュダウンオートマトン」です。与えられた言語を生成する文法を作る問題、導出木を描く問題、文法があいまいかどうかを判定する問題が出ます。

第3章「言語と形式文法」では、文法の4つの階層と、それぞれに対応するオートマトンを整理します。

第5章のチューリング機械と、第6章「決定問題」は、計算可能性を扱います。出題する志望先とそうでない志望先が分かれるため、過去問に出ていなければ、概要をつかむ程度で構いません。

学習期間の目安約1か月
到達の目安非決定性のオートマトンを決定性に変換し、状態数を最小化できる状態が目安です。
仕上がりのチェック項目

次の問いに答えられるかを確かめてください。

  • 正規表現から、対応する有限オートマトンを作れるか
  • ある言語が正規言語でないことを、反復に関する補題で示せるか
  • 簡単な言語について、文脈自由文法を書けるか
注意点と、次の一手
注意点

理論的な内容で、証明が多く含まれます。計算量理論(PやNPなどのクラス)は、中心的な話題ではないため、出題される場合は別の本で補ってください。

補うべき範囲と、次に進む本

読み終えたら、志望先の過去問で、変換と構成の問題を繰り返し解きます。

学習ルート
いまここ オートマトン・言語理論(第2版・新装版)森北出版オートマトン・言語理論(第2版・新装版)の表紙 オートマトン・言語理論(第2版・新装版)
この本の次に 志望先の過去問に進みます。
同じレベルの別の選択肢

情報科学・基礎の参考書をすべて見る

購入はこちら

期間限定!入会金無料キャンペーン!

11月30日までのお申し込みで、
入会金30,000円が無料!

また、ご満足いただけない場合は安心の全額返金保証制度あり!

無料体験講義のお申し込み

下記に必要事項を記入の上、【送信】を押してください。
数日以内に担当のものからメールでお返事させていただきます。
※迷惑メール設定を解除いただくようお願いいたします。

    院試塾INPASSのサービス内容は、こちらからご確認いただけます。

    INPASSの詳細を見る

    情報の最終確認日:2026-11-17

    タイトルとURLをコピーしました