オートマトンとは？状態遷移図・有限オートマトン・DFAとNFAを基礎から理解しよう

はじめに

コンピュータの処理では、

現在の状態と、与えられた入力によって次の動作が決まる

という仕組みがよく使われます。

例えば、自動販売機を考えてみましょう。

お金が入っていない状態
↓
100円を入れる
↓
100円入っている状態
↓
さらに100円を入れる
↓
200円入っている状態

このように、

ある状態から、入力によって別の状態へ移動する仕組み

を数学的なモデルとして表したものが**オートマトン（Automaton）**です。

この記事では、

オートマトンとは何か
状態
入力
状態遷移
状態遷移図
有限オートマトン
DFA
NFA
開始状態・受理状態
文字列の受理
正規表現との関係

について順番に整理していきます。

1. オートマトンとは

**オートマトン（Automaton）**とは、

入力を受け取りながら状態を変化させ、決められた動作を行う数学的なモデル

です。

難しそうに聞こえますが、基本的な考え方はシンプルです。

現在の状態
+
入力
↓
次の状態

というルールを繰り返します。

例えば信号機なら、

青
↓
時間が経過
↓
黄
↓
時間が経過
↓
赤

のように状態が変化します。

オートマトンでは、このような状態の変化に注目します。

🍯 はちみつメモ

オートマトン = 入力によって状態が変化する仕組みを表したモデル

2. 「状態」とは

オートマトンを理解するうえで最も重要なのが**状態（State）**です。

状態とは、

現在どのような状況にあるのか

を表したものです。

例えば自動販売機なら、

0円入っている状態
100円入っている状態
200円入っている状態

などが状態になります。

ドアのロックなら、

ロック状態
アンロック状態

の2つの状態を考えることもできます。

オートマトンでは通常、それぞれの状態に、

q0
q1
q2

のような名前を付けます。

3. 入力とは

オートマトンでは、外部から与えられる情報を入力として扱います。

例えば自動販売機なら、

100円を入れる
500円を入れる
商品ボタンを押す

などが入力になります。

文字列を扱うオートマトンなら、

0
1

や、

a
b

などの文字が入力になります。

このような入力として使用できる記号の集合を入力アルファベットと呼びます。

例えば、

Σ = {0, 1}

なら、入力として0と1を使うという意味です。

4. 状態遷移とは

ある状態から別の状態へ移動することを**状態遷移（State Transition）**といいます。

例えば、

q0
↓ 0を入力
q1

なら、

q0の状態で0を入力するとq1へ移動する

という意味です。

オートマトンでは、

現在の状態
+
入力
↓
次の状態

という状態遷移のルールを定義します。

5. 状態遷移図

状態と状態遷移を図として表したものを状態遷移図といいます。

例えば、

       0
   ┌───────→ q1
   │
  q0
   ↑
   └───────
       1

のように、

状態を丸
状態遷移を矢印
矢印の近くに入力

を書いて表現します。

例えば、

q0 --0--> q1

なら、

q0で0を入力するとq1になる

という意味です。

状態遷移図を見ると、どの入力によってどの状態へ移るのかを視覚的に理解できます。

6. 自動販売機を状態遷移で考える

例えば、200円の商品を販売する自動販売機を簡単に考えてみます。

状態を、

q0：0円
q1：100円
q2：200円

とします。

100円硬貨だけを使えるとすると、

q0 --100円--> q1

q1 --100円--> q2

となります。

つまり、

0円
↓ 100円投入
100円
↓ 100円投入
200円

です。

このように現実の動きを、

状態と入力だけに注目して単純化する

のがオートマトンの考え方です。

7. 有限オートマトンとは

オートマトンの中でも、状態の数が有限個しかないものを**有限オートマトン（Finite Automaton）**といいます。

例えば、

q0
q1
q2

という3つの状態だけを持つなら有限オートマトンです。

有限オートマトンでは主に、

現在の状態
入力
次の状態
開始状態
受理状態

などを定義します。

有限オートマトンは特に、

入力された文字列が、ある条件に当てはまるか

を判定するためによく使われます。

8. 開始状態

オートマトンが処理を開始するとき、最初にいる状態を**開始状態（Initial State）**と呼びます。

状態遷移図では、外側から矢印を付けて表すことがあります。

→ q0

この場合、q0が開始状態です。

入力を読み込む前は、まずこの状態からスタートします。

9. 受理状態

入力をすべて読み終えたとき、

この文字列は条件を満たしている

と判定する状態を**受理状態（Accept State / Final State）**と呼びます。

状態遷移図では、一般的に二重丸で表します。

例えば、

q0 → q1 → ((q2))

なら、q2が受理状態です。

入力を最後まで読み終えたときにq2にいれば、その文字列は受理されるといいます。

10. 文字列を受理するとは

例えば、

最後が1で終わる2進数の文字列を受理する

オートマトンを考えてみます。

入力は、

Σ = {0, 1}

です。

状態を、

q0：最後に読んだ文字が1ではない
q1：最後に読んだ文字が1

とします。

状態遷移は、

q0 --0--> q0
q0 --1--> q1

q1 --0--> q0
q1 --1--> q1

です。

そして、

q0：開始状態
q1：受理状態

とします。

11. 実際に文字列を入力してみる

例えば、

を入力してみます。

最初はq0です。

開始
q0

最初の1を読みます。

q0 --1--> q1

次に0を読みます。

q1 --0--> q0

最後に1を読みます。

q0 --1--> q1

結果は、

q1

です。

q1は受理状態なので、

は受理されます。

実際に最後の文字も1なので、条件と一致しています。

12. 受理されない例

今度は、

を入力します。

開始：q0

1 → q1
1 → q1
0 → q0

入力をすべて読み終えたとき、

q0

になっています。

q0は受理状態ではありません。

したがって、

は受理されません。

🍯 はちみつメモ

オートマトンでは、

入力を全部読み終えたときに受理状態にいるか

が重要です。

13. 状態遷移表

状態遷移は図だけでなく、状態遷移表として表すこともできます。

先ほどの例なら、

現在の状態	入力0	入力1
q0	q0	q1
q1	q0	q1

となります。

状態遷移図と状態遷移表は、表現方法が違うだけで、基本的には同じ情報を示しています。

試験問題では、

状態遷移図
状態遷移表

のどちらも登場する可能性があるため、両方読めるようにしておきましょう。

14. DFAとは

有限オートマトンの代表的な種類がDFAです。

DFAは、

Deterministic Finite Automaton

の略で、日本語では決定性有限オートマトンと呼ばれます。

DFAでは、

現在の状態と入力が決まれば、次の状態が必ず1つに決まる

という特徴があります。

例えば、

q0で0を入力
↓
必ずq1

というようになります。

同じ状態・同じ入力に対して、複数の移動先が存在することはありません。

15. DFAを簡単に考える

例えば、

q0 --0--> q0
q0 --1--> q1

というルールがある場合、

q0で1を入力すれば、次は必ずq1です。

現在：q0
入力：1
↓
次：q1

となり、迷うことはありません。

これが決定性です。

🍯 はちみつメモ

DFAは、

現在の状態 + 入力 → 次の状態が必ず1つ

と覚えましょう。

16. NFAとは

もう一つの代表的な有限オートマトンがNFAです。

NFAは、

Nondeterministic Finite Automaton

の略で、日本語では非決定性有限オートマトンと呼ばれます。

NFAでは、ある状態で同じ入力を受け取ったときに、

複数の状態へ遷移できる場合があります。

例えば、

        ┌→ q1
q0 --a--|
        └→ q2

のように、

q0でaを入力
↓
q1またはq2

という状態遷移が存在できます。

17. ε遷移

NFAでは、入力文字を読み込まずに状態を移動できる場合があります。

これを**ε遷移（イプシロン遷移）**と呼びます。

例えば、

q0 --ε--> q1

なら、

入力を1文字も消費せずにq0からq1へ移動できる

という意味です。

DFAでは基本的にこのような遷移は使いません。

18. DFAとNFAの違い

DFAとNFAを整理すると、

項目	DFA	NFA
日本語	決定性有限オートマトン	非決定性有限オートマトン
同じ入力に対する遷移先	1つ	複数の場合がある
ε遷移	なし	あり得る
状態遷移	一意に決まる	複数候補を持てる

NFAの方が自由に状態遷移を書けるため、複雑な条件を簡潔に表現できる場合があります。

19. NFAでも本当に判定できるの？

NFAでは複数の遷移先があるため、

「どっちに行けばいいの？」

と感じるかもしれません。

NFAでは、可能な遷移をすべて考えます。

その中の少なくとも1つの経路が、入力をすべて読み終えたときに受理状態へ到達すれば、その文字列を受理します。

つまり、

複数のルート
↓
どれか1つでも受理状態へ到達
↓
受理

という考え方です。

20. DFAとNFAの表現能力

DFAとNFAは仕組みこそ違いますが、

受理できる言語の範囲は同じ

です。

つまり、NFAで表現できるものはDFAでも表現できます。

逆も同様です。

NFAをDFAへ変換することもできます。

そのため、

DFA
NFA

は表現方法こそ異なりますが、どちらも正規言語と呼ばれる種類の言語を扱います。

21. 「言語」とは

オートマトンの分野では「言語」という言葉が登場します。

ここでいう言語は、日本語や英語のことではありません。

ある規則に従った文字列の集合

を意味します。

例えば、

0と1からなる文字列で、
最後が1のもの

という条件なら、

などが含まれます。

このような文字列の集合を形式言語と呼びます。

22. 正規言語とは

有限オートマトンによって受理できる言語を**正規言語（Regular Language）**と呼びます。

例えば、

0と1からなる文字列で最後が1

という言語は有限オートマトンで判定できます。

そのため、これは正規言語です。

正規言語は、次に説明する正規表現とも深い関係があります。

23. 正規表現との関係

**正規表現（Regular Expression）**は、

文字列のパターンを表現する方法

です。

例えば、

a*

なら、

空文字
a
aa
aaa
aaaa

のように、aが0回以上繰り返される文字列を表します。

有限オートマトンと正規表現は、どちらも正規言語を表現できます。

つまり、

正規表現
   ↕
有限オートマトン
   ↕
正規言語

という関係があります。

24. 正規表現の基本

オートマトンを理解するうえで、簡単な正規表現も押さえておきましょう。

例えば、

a*

の*は、

直前の文字が0回以上繰り返される

ことを表します。

ab*

なら、

a
ab
abb
abbb

などが該当します。

また、

a|b

は、

a または b

を表します。

25. オートマトンはどこで使われる？

オートマトンは理論だけのものではありません。

実際のITでは、

文字列検索
字句解析
コンパイラ
正規表現
通信プロトコル
状態管理
ゲームのキャラクター制御
UIの状態管理

など、さまざまな場所につながっています。

例えばログイン処理なら、

未ログイン
↓ ログイン成功
ログイン済み
↓ ログアウト
未ログイン

という状態遷移として考えることもできます。

26. 状態遷移図を読むコツ

オートマトンの問題では、複雑な状態遷移図が登場することがあります。

そのときは一気に答えを考えず、

開始状態を確認
↓
入力を左から1文字読む
↓
矢印を1つ進む
↓
次の文字を読む
↓
最後まで繰り返す
↓
受理状態か確認

という順番で追っていきましょう。

例えば入力が、

なら、

1
↓
0
↓
1
↓
1
↓
0

と必ず1文字ずつ状態を追うのがポイントです。

27. オートマトンの問題でよくある考え方

試験では、

このオートマトンが受理する文字列はどれか

という問題が出ることがあります。

この場合は、

開始状態を確認する
選択肢の文字を左から読む
入力ごとに状態を移動する
最後に受理状態になっているか確認する

という方法で解けます。

また、

このオートマトンが表している条件は何か

という問題もあります。

例えば、

最後の文字が1
1の個数が偶数
00を含む
特定の文字列で終わる

などの規則を、状態遷移から読み取ります。

28. 「1の個数が偶数」を判定するオートマトン

少し具体的な例を見てみましょう。

0と1からなる文字列について、

1の個数が偶数なら受理する

オートマトンを考えます。

状態を、

q0：1の個数が偶数
q1：1の個数が奇数

とします。

最初は1が0個なので、q0からスタートします。

0を入力しても1の個数は変わらないので、

q0 --0--> q0
q1 --0--> q1

です。

1を入力すると偶数と奇数が入れ替わるため、

q0 --1--> q1
q1 --1--> q0

となります。

q0を受理状態にすれば、

1の数が偶数の文字列だけを受理するオートマトン

になります。

29. 状態には「覚えておきたい情報」を持たせる

先ほどの例で重要なのは、オートマトンが1の個数そのものを記憶しているわけではないことです。

例えば、

1が2個
1が4個
1が100個

を全部別々の状態にしているわけではありません。

必要なのは、

偶数なのか
奇数なのか

だけです。

そのため、

q0：偶数
q1：奇数

の2状態だけで判定できます。

つまり状態とは、

これから正しく判定するために必要な情報だけを覚えているもの

と考えると理解しやすくなります。

🍯 はちみつメモ

状態を考えるときは、

「過去の入力について、何だけ覚えておけば判定できる？」

と考えるのがコツです。

30. オートマトン全体を整理しよう

ここまでの関係を整理すると、

入力
 ↓
開始状態からスタート
 ↓
1文字ずつ入力を読む
 ↓
状態遷移
 ↓
最後の状態を確認
 ↓
受理状態なら受理

となります。

有限オートマトンには、

DFA
↓
次の状態が1つに決まる

NFA
↓
複数の遷移先を持てる

という種類があります。

そして、

有限オートマトン
     ↕
正規表現
     ↓
正規言語

という関係があります。

31. 試験で押さえたいポイント

応用情報技術者試験では、特に次のポイントを押さえておきましょう。

状態遷移

現在の状態 + 入力
↓
次の状態

という仕組みです。

開始状態

入力を読み込む前にいる状態です。

受理状態

すべての入力を読み終えたとき、条件を満たしていることを表す状態です。

DFA

現在の状態 + 入力
↓
次の状態が必ず1つ

となる有限オートマトンです。

NFA

現在の状態 + 入力
↓
複数の遷移先を持てる場合がある

有限オートマトンです。

ε遷移を持つ場合もあります。

DFAとNFA

仕組みは違いますが、表現できる言語の範囲は同じです。

正規言語

有限オートマトンによって受理できる言語です。

正規表現

文字列のパターンを表現する方法で、有限オートマトンと同じ正規言語を表現できます。

まとめ

今回は、オートマトンについて学びました。

この記事で覚えること

オートマトンは入力によって状態が変化する数学的モデル
状態は現在の状況を表す
状態から別の状態へ移ることを状態遷移という
状態遷移図では状態を丸、遷移を矢印で表す
状態の数が有限個のものを有限オートマトンという
開始状態から処理をスタートする
入力終了時に受理状態なら文字列を受理する
DFAでは同じ状態・入力に対する次の状態が1つに決まる
NFAでは複数の遷移先を持てる
NFAではε遷移を使う場合がある
DFAとNFAが表現できる言語の範囲は同じ
有限オートマトンが受理する言語を正規言語という
正規表現と有限オートマトンはどちらも正規言語を表現できる

オートマトンでは、用語だけを暗記するより、

現在の状態
+
1つの入力
↓
次の状態

という動きを実際に追うことが重要です。

状態遷移図が出てきたら、入力を左から一つずつ読んで状態を移動し、最後に受理状態へ到達しているか確認しましょう。

🍯 はちみつメモ

オートマトン = 入力に応じて状態を変化させる仕組み

問題では、

開始状態 → 入力を1文字ずつ読む → 状態を移動 → 最後に受理状態か確認

の順番で追えばOKです。

DFA = 次の状態が1つに決まる
NFA = 複数の遷移先を持てる