有限状態機械アニメーター

ライブの状態遷移図でDFAの遷移を1ステップずつ確認

計算例 — 有限状態機械アニメーター

次の記号	'1'

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

有限の記憶、無限の文字列 🖖

有限オートマトンは固定された記憶——その状態集合——しか持ちません。入力文字列がどれほど長くても、マシンが使う記憶量は状態数を超えることはありません。だからこそDFAは無制限に数を数えることができないのです。任意の整数を「記憶」する状態は存在しません。反復補題はこれを厳密に示します。DFAが受理する十分に長い文字列は、中間部分を任意の回数繰り返しても受理されたままです。反復できない言語（aとbの個数が等しいaⁿbⁿなど）にはプッシュダウンオートマトンやチューリングマシンが必要です。マイヒル-ネロードの定理は正確な最小値を与えます——状態数は入力接頭辞の区別可能な同値類の数に等しくなります。

一つのトークン、一本の道 🖖

決定性有限オートマトンとは、状態を矢印でつないだラベル付きの図にすぎません。どの状態でも、どの入力記号に対しても、たどる矢印はちょうど一本だけなので、選択の余地はありません。機械は文字列を左から右へ一度だけ読み、最後に一つの状態にたどり着きます。その最終状態が受理状態と印されていれば、その入力はその言語に属します。矢印に沿ってトークンを滑らせるだけでたどれる——このツールが見せてくれるのは、まさにそれです。

ニューロンのモデルから生まれた 🖖

有限オートマトンは計算機科学から始まったのではありません。1943年、ウォーレン・マカロックとウォルター・ピッツはニューロンを互いに配線された単純なオン/オフの素子として記述し、これが有限状態機械の最初の数学的モデルとなりました。1951年、スティーブン・クリーネはそうした『神経網』がどんなパターンを認識できるかを分析し、それを正規事象と名づけました——今日の正規表現の起源です。つまり、あなたがここで一歩ずつたどっているオートマトンは、脳がどう計算するかを説明しようとした試みの直系の子孫なのです。

全プロセスの詳細解説

状態数をどれだけ与えても、有限機械が0と1の数を対応付けられない理由 8 ステップ
このページにあるパリティマシンは2つの状態を持ち、101101という6つのシンボルを読み込んでも、3つ目の状態を必要とすることは決してありません。600万個のシンボルを与えても、やはり必要なのは2つの状態だけです。では、固定された数の状態を持つ機械にできないこととは何でしょうか？アンド、機械を見つけられなかったというだけでなく、機械が存在しないことをどのように証明するのでしょうか？
1. 手元にある機械を観察してみましょう。パリティは状態 e から始まり、1 を読み込むたびに反転します。6つのシンボルを読み終えた後、機械は再び e に戻り、入力は受理されます。途中で累積されたものは何もありません。6番目のシンボルにおける機械の状態は、1番目のシンボルにあった時と全く同じ状態です。
  
  $e 1 o 0 o 1 e 1 o 0 o 1 e$
2. それが利用できるリソースのすべてです。DFAのメモリとは、自身が現在存在する状態そのものであり、それ以外にはありません。カウンターも、スタックも、書き込めるテープもありません。任意の接頭辞を読み終えた後、機械がその接頭辞について知っていることのすべては、全 k 個の状態のうち現在どの状態を占めているかということだけです。
  
  $∣ Q ∣ = k ⟹ at most k distinguishable pasts$
3. そこで、明らかにそれ以上の能力を必要とするものを見つけてみましょう。任意の個数の 0 の後に、それと全く同じ個数の 1 が続く文字列を考えます。01 は該当し、0011 も該当しますが、001 は該当せず、0110 も該当しません。
  
  $L = {0^{n} 1^{n} : n \geq 0}$
4. k 個の状態を持つDFAがこれを認識すると仮定します。機械がどのような構造をしているかを尋ねてはいけません――それが明かされることはありません。ただ、0個から k 個までの 0 で構成される k+1 個の接頭辞を機械に与え、それぞれがどの状態に機械を留めるかを記録するだけです。
  
  $0^{0}, 0^{1}, \dots, 0^{k} ⟶ k + 1 strings into k states$
5. 鳩ノ巣原理です。接頭辞の数が状態の数よりも多いため、そのうちの2つは同じ状態に行き着きます。i が j より小さいとして、それらを 0ⁱ と 0ʲ と呼びましょう。その瞬間から、機械は両者を区別できなくなります。設計が不十分だからではありません。状態だけが機械の持つすべてであり、その2つの文字列が全く同じ状態をもたらしたからです。
  
  $δ^{*} (q_{0}, 0^{i}) = δ^{*} (q_{0}, 0^{j}), i < j \leq k$
6. ここで、両方の接頭辞の続きに同じもの、すなわち i 個の 1 を与えます。開始状態が同じで、シンボルも同じであるため、終了状態も同じになり、判定結果も同じになります。機械にはそれ以外の挙動をとる余地がありません。
  
  $δ^{*} (q_{0}, 0^{i} 1^{i}) = δ^{*} (q_{0}, 0^{j} 1^{i})$
7. しかし、2つの判定結果は異なっていなければなりません。0ⁱ1ⁱ は個数が一致しているため言語に属しますが、0ʲ1ⁱ は j が i と異なるため属しません。一方は受理され、他方は拒否されなければなりませんが、機械は両者に同じ答えを出してしまいます。崩れ去るのは、そのような機械が存在するという前提です。
  
  $0^{i} 1^{i} \in L, 0^{j} 1^{i} \in / L$
8. この論証をもう一度読み返し、そこに現れなかったものに注目してください。それは k の具体的な値です。パリティマシン自身のサイズである2であっても、20億であっても、いずれにせよ k+1 個の接頭辞は k 個の状態数より多くなります。ただし、n に上限を設けると、言語は途端に有限状態言語になります。N まで対応させるには 2N+2 個の状態が必要となるため、N = 10 の場合は 22 個、N = 100 の場合は 202 個となります。
  
  ${0^{n} 1^{n} : n \leq N} needs 2 N + 2 states$
解答

どのようなサイズであっても、これを受理する有限オートマトンは存在しません。この証明は機械がどのように構成されているかについての知識を一切必要とせず、k+1 個のものが k 個の場所に入る際には必ず2つ以上が同じ場所を共有しなければならないこと、そして状態を共有することは記憶の消失（忘却）を意味することのみに依拠しています。パリティマシンはこれと同じ現象を縮小版で示しています。0、続いて 00、さらに 000 を入力しても、3つすべてが機械を e の状態に留めます。なぜなら、この機械は 0 を全く見ていないからです。

難しさの本質は上限の有無にあります。N までを対応させることは簡単で、2N+2 個の状態があればよく、到達したいシンボルが1つ増えるごとにもう1対の状態を追加すれば済みます。しかし、その数はどこまでも増え続けるため、特定の N に対する機械は存在しても、すべての N に対応する単一の機械は存在しません。このギャップこそが「有限メモリ」の意味するところであり、DFAの次に来るものがスタック（境界のない記憶装置）を追加することで定義される理由です。スタックが追加されたのは、まさにその欠如がもたらす限界を解消するためです。

参考文献 (2)

Insight block 3 — the nerve-net model the finite automaton descends from: W. S. McCulloch and W. Pitts, "A logical calculus of the ideas immanent in nervous activity." Bulletin of Mathematical Biophysics 5(4), 115–133, 1943.
Insight block 1 — the theorem that fixes the minimum state count: A. Nerode, "Linear automaton transformations." Proceedings of the American Mathematical Society 9(4), 541–544, 1958.

42Math チーム · 更新 2026-06-03

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

01で終わる - 接尾辞認識器は、01で終わる文字列を受理する。
拒否（10で終わる） - 却下 (末尾が10)
1の個数が偶数 ✓ - パリティオートマトンは、1の個数が偶数の2進文字列を受理する。
1の個数が奇数 ✗ - 入力には三つの1が含まれ、パリティ機械はその一つひとつで状態を反転させます（e、o、o、e、o）。最終的にoで停止し、拒否されます。ここで数が数えられているわけではありません。この機械が持つ状態は二つだけであり、それで十分なのです。文字列がどれほど長くても、これまでの数が奇数であるかどうか。それこそが、記憶に留める価値のある唯一の事実だからです。
101を含む ✓ - 四つ目の記号で機械はs3に到達し、そこから抜け出せなくなります。0を受け取っても1を受け取っても、s3からs3へと遷移するからです。さらに三つの記号が通り過ぎますが、そのすべてに対する判定はすでに確定しています。入力が尽きる前に、いつ条件を満たしたかを記憶することなく、DFAが受理を確定させる仕組み。それがトラップ状態です。
101を含まない ✗ - s2で拒否されました。凡例にある『10を読み込み済み — あと一記号』の状態です。最後にもう一つ1が続いていればパターンが完成し、機械は永遠にs3に固定されていたことでしょう。到達した状態を見れば、完成までどれほど迫っていたかが読み取れます。受理か拒否かという結果だけからは、決して得られない情報です。