オートマット（automaton）とは、入力として与えられる文字列を順に読み取り、状態を切り替えながら最終的に「受理するか（受理状態に到達するか）」または「拒否するか」を判定する計算モデルです。直感的には、テキスト処理を行う機械やルールベースの判定装置を頭の中で抽象化したものだと言えます。しかしオートマットが面白いのは、単なる「文字列をふるいにかける装置」にとどまらず、計算可能性・形式言語・理論計算機科学の中心に位置し、しかも“限界”や“構造の美しさ”まで見せてくれる点にあります。特にここでは、「有限オートマトンが表せるもの／表せないもの」というテーマを軸に、なぜそれが計算の限界を見抜く視点になるのかを長めに掘り下げます。
まず、オートマトンは状態という概念で「記憶」を表します。入力を一文字ずつ読み進めるたびに、オートマトンは現在の状態と読み取った記号に基づいて次の状態へ遷移します。したがって、その装置が持てる“記憶量”は、状態の個数で上限が決まります。有限オートマトン（DFA: Deterministic Finite Automaton や NFA: Nondeterministic Finite Automaton）は、状態数が有限であるため、入力長がいくら伸びても状態数は増えません。その結果、有限オートマトンは「入力のある性質」をチェックするとしても、永続的に増え続ける情報（たとえば“何回目か”を入力長に比例して追跡するような情報）には限界が生まれます。
この限界は、表せる言語の種類によってはっきりと現れます。たとえば、DFAで判定できる言語は「正則言語（regular language）」と呼ばれ、正則表現（正規表現）や正則文法とも対応関係があります。ここが重要で、有限オートマトンは単なる理論上のモデルではなく、現実の仕様にも深く結びついています。たとえば、ネットワークのパケット検査、ログの形式検査、文字列の妥当性チェックなどは、しばしば正則言語で表現できる範囲に収まっています。なぜなら、多くの現実的なパターンは「有限個の条件」に還元できることが多いからです。たとえば「末尾が “.png” である」「数字が3桁で区切り記号の有無が決まっている」などは、必要な情報が有限の状態で追えるため、有限オートマトンで自然に表せます。
一方で、有限オートマトンには苦手な性質もあります。典型例が「n回現れたものが後でもうn回現れるか」「同じ長さの対応ができているか」「中身の数が一致しているか」といった、入力長に比例して必要な情報が増えていくタイプの性質です。有限オートマトンは状態が有限なので、入力の途中で“長さに応じて増える情報”を保持し続けることができません。直感的に言えば、「先に見たものの個数を数え上げる」ことは、数を際限なく増やさないと成立しない性質があるため難しくなります。もっとも、有限オートマトンが完全に何も数えられないわけではありません。たとえば「3の倍数回だけ現れる」や「長さが偶数である」なら、状態を適切に用意することで判定できます。これは必要な“数え方”が剰余類（mod）の範囲に収まるからです。有限オートマトンは本質的に、入力がどの剰余状態にいるかのような“有限な情報”に変換できる性質に強いわけです。
この「状態が有限であること」が計算の限界に直結する理由は、数学的にも非常にきれいに整理されています。代表的にはポンプ補題（pumping lemma）があります。これは、正則言語であればある長さ以上の文字列は「どこかを繰り返しても（一定の範囲で）同じ性質が保たれる」という形の性質を持つ、という主張です。有限オートマトンでは入力を読む過程で状態を遷移しますが、十分長い入力を読むと必ず同じ状態が繰り返し訪れる区間が生まれます（状態数が有限だからです）。そのため、その区間を繰り返しても到達する受理／拒否の結論が変わらないケースが生じます。この現象を一般化して「正則言語では、ある種の部分を繰り返しても言語の所属が変わらない」という必要条件を導くのがポンプ補題です。逆に言えば、その必要条件を満たさない言語の候補は正則ではないことが証明できます。つまり、ポンプ補題は「有限オートマトンで表せる可能性があるかどうか」を見抜くための強力な道具になります。
ここでさらに面白いのは、「オートマトンで表せない性質」を表すために、オートマトンのモデルを拡張していくと、必要な“記憶の形式”が自然に見えてくる点です。たとえば、スタック（スタックメモリ）を持つオートマトンであるプッシュダウンオートマトン（PDA）は、入れ子構造の対応を扱えます。括弧の対応（開きと閉じの整合性）などがその典型です。スタックは入力長に応じて必要に応じて増減できるため、「先に見たものの個数」と「後で現れるものの個数」の対応のような性質を比較的素直に扱えます。さらに計算が必要になれば、チューリングマシンのようなより強力なモデルへと進みます。こうして、オートマトンの系譜をたどると「何を記憶として持つか（状態だけか、スタックか、テープのような無限記憶か）」が計算能力そのものと結びついていることが見えてきます。
この視点で見ると、有限オートマトンの限界は単なる欠点ではなく、分類学的な意味を持ちます。有限オートマトンが扱える言語（正則言語）を境界として、それ以上の計算能力が必要な言語は“構造の性質”として区別されます。たとえば「括弧が正しく閉じる」や「同数対応」などは、正則ではありません。なぜなら、これらは一般に入力長に比例した比較・対応が必要になり、有限状態だけでは情報が足りないからです。つまり、オートマットで表せる／表せないという話は、結局「入力に対してどれだけの記憶が要るか」という計算理論の本質に触れています。
そして、このテーマが“興味深い”理由は、理論の抽象度が高いのに、最終的に現実の応用にも直結している点です。たとえばソフトウェア工学では、正則表現とオートマトンが密接に結びついていて、コンパイラやパーサ生成器の内部でも活用されています。検索やフィルタリングの実装は、しばしば入力を左から右へ読み進めながら状態を更新することで成立します。さらに、正則言語かどうかの判断ができると、設計段階で「この条件は単純な状態遷移だけで実装できるのか、それとも別の仕組みが必要か」を見積もれます。有限オートマトンで表せない要件を最初から認識しておくと、無駄な試行錯誤を避けられるだけでなく、必要なデータ構造やアルゴリズム（スタックやより強い計算モデルに相当するもの）へ早く到達できます。
まとめると、「オートマットが示す計算の限界」というテーマは、単に“難しい理論がある”という話ではありません。有限オートマトンは有限状態という有限の記憶を使って言語の判定を行うため、表せる性質には明確な境界がある。その境界はポンプ補題のような理論的結果によって厳密化され、表現できない性質は、より強力な記憶（スタックや計算機械）を必要とすることとして見えてくる。さらにその境界は、正則表現や現実の検査・処理へとつながり、設計上の指針にもなる。オートマットとは、計算の“できること”だけでなく、“できないこと”を同じくらい美しく整理して見せてくれるモデルなのです。