# オートマトンと正規言語｜DFA・NFA・部分集合構成・正規表現・反復補題

> 決定性・非決定性有限オートマトンの定義、部分集合構成によるNFAからDFAへの変換、正規表現との同値性、正規言語の閉包性と反復補題を、3で割り切れる2進数や a^n b^n の計算例で解説します。

- HTML版（正規URL）: https://inshihub.com/basics/theory-of-computation/automata-regular-languages
- 科目: [計算理論](https://inshihub.com/basics/theory-of-computation)（大学基礎課程の数学・物理・化学・生物・情報）
- 最終更新: 2026-11-16

有限オートマトンは、有限個の状態と、入力記号ごとの状態遷移で文字列を受理するかを決める機械である。決定性（DFA）と非決定性（NFA）は受理できる言語のクラスが同じで、NFA は部分集合構成で DFA に変換できる。DFA で受理できる言語を正規言語といい、正規表現で表せる言語と一致する。ある言語が正規でないことは、反復補題の条件が成り立たないことを示して証明する。

## 言語・DFA・NFA・正規表現の定義

### 定義：アルファベットと言語

空でない有限集合 $\Sigma$ をアルファベット、その要素の有限列を文字列（語）という。長さ0の文字列を $\varepsilon$、すべての文字列の集合を $\Sigma^*$ と書く。$\Sigma^*$ の部分集合を言語という。言語 $L_1, L_2$ の連接は $L_1L_2 = \{uv \mid u \in L_1,\ v \in L_2\}$、クリーネ閉包は $L^* = \bigcup_{k \ge 0} L^k$（$L^0 = \{\varepsilon\}$）である。

### 定義：決定性有限オートマトン（DFA）

DFA は5つ組 $M = (Q, \Sigma, \delta, q_0, F)$ で、$Q$ は有限の状態集合、$\delta: Q \times \Sigma \to Q$ は遷移関数、$q_0 \in Q$ は初期状態、$F \subseteq Q$ は受理状態の集合である。遷移を文字列に広げた $\hat\delta(q, \varepsilon) = q$、$\hat\delta(q, wa) = \delta(\hat\delta(q, w), a)$ を使い、$M$ が受理する言語を

$$L(M) = \{ w \in \Sigma^* \mid \hat\delta(q_0, w) \in F \}$$

と定める。

### 定義：非決定性有限オートマトン（NFA）

NFA は遷移関数を $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$（状態の集合への写像）に替えたものである。入力を読み終えたとき、とり得る状態のどれか1つでも $F$ に入っていれば受理する。$\varepsilon$ 遷移は入力を読まずに状態を移る。

### 定義：正規表現

$\emptyset$、$\varepsilon$、各 $a \in \Sigma$ は正規表現で、$r, s$ が正規表現なら $(r + s)$、$(rs)$、$(r^*)$ も正規表現である。表す言語はそれぞれ $\emptyset$、$\{\varepsilon\}$、$\{a\}$、和集合、連接、クリーネ閉包とする。$+$ を $|$ と書く流儀もある。

## 部分集合構成・クリーネの定理・閉包性

### 定理・法則：部分集合構成（NFA と DFA の等価性）

条件：

$N = (Q, \Sigma, \delta, q_0, F)$ は NFA（$\varepsilon$ 遷移を含んでよい）。$E(S)$ は状態集合 $S$ から $\varepsilon$ 遷移だけでたどれる状態全体（$\varepsilon$ 閉包）。

主張：

状態集合を $2^Q$、初期状態を $E(\{q_0\})$、遷移を $\delta_D(S, a) = E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr)$、受理状態を $F$ と交わる集合全体とする DFA $D$ は、$L(D) = L(N)$ を満たす。

要点：

DFA の状態数は最悪 $2^{|Q|}$ になる。実際の構成では初期状態から到達できる集合だけを作る。

### 定理・法則：クリーネの定理

条件：

アルファベット $\Sigma$ 上の言語 $L$。

主張：

$L$ がある DFA で受理されることと、$L$ がある正規表現で表されることは同値である。この言語のクラスを正規言語という。

要点：

正規表現から $\varepsilon$-NFA へはトンプソン構成、DFA から正規表現へは状態除去法や $R_{ij}^{(k)}$ の漸化式で変換する。

### 定理・法則：正規言語の閉包性

条件：

$L_1, L_2$ は同じアルファベット $\Sigma$ 上の正規言語。

主張：

$L_1 \cup L_2$、$L_1 L_2$、$L_1^*$、補集合 $\Sigma^* \setminus L_1$、$L_1 \cap L_2$、反転 $L_1^R$ はどれも正規言語である。

要点：

補集合は完全な DFA（すべての状態とすべての記号に遷移がある）で受理状態と非受理状態を入れ替えて作る。NFA のまま入れ替えても補集合にならない。共通部分は2つの DFA の直積で作る。

### 定理・法則：最小 DFA（マイヒル・ネローデの定理）

条件：

$L \subseteq \Sigma^*$。$x \equiv_L y$ を「すべての $z$ で $xz \in L \iff yz \in L$」で定める。

主張：

$L$ が正規であることと、$\equiv_L$ の同値類が有限個であることは同値である。正規なら、同値類の個数が $L$ を受理する DFA の最小状態数で、最小 DFA は状態の名前を除いて一意である。

## DFA の設計と部分集合構成の計算例

### 計算例：3で割り切れる2進数を受理する DFA

$\Sigma = \{0, 1\}$ の文字列を上位桁から読む2進数とみなし、値が3で割り切れる文字列を受理する DFA を作れ（$\varepsilon$ は値0とみなす）。

解答：

状態を、それまでに読んだ値を3で割った余り $q \in \{0, 1, 2\}$ とする。値 $v$ の後ろに $a$ を付けると値は $2v + a$ になるので

$$\delta(q, a) = (2q + a) \bmod 3$$

とし、初期状態 $0$、受理状態 $\{0\}$ とする。遷移表は $\delta(0,0) = 0$、$\delta(0,1) = 1$、$\delta(1,0) = 2$、$\delta(1,1) = 0$、$\delta(2,0) = 1$、$\delta(2,1) = 2$。

検算：

$1001$（9）は状態 $0 \to 1 \to 2 \to 1 \to 0$ で受理、$1011$（11）は $0 \to 1 \to 2 \to 2 \to 2$ で拒否する。長さ1〜12のすべての文字列で、受理と「値が3の倍数」が一致することを実装で確かめた。

### 計算例：部分集合構成で NFA を DFA に変換する

「後ろから2文字目が1」の文字列を受理する NFA：状態 $p$（初期）、$q$、$r$（受理）、遷移 $p \xrightarrow{0,1} p$、$p \xrightarrow{1} q$、$q \xrightarrow{0,1} r$ を DFA に変換せよ。

解答：

$\{p\}$ から始め、到達できる集合だけを作る。

$$\begin{array}{c|cc} & 0 & 1 \\ \hline \{p\} & \{p\} & \{p,q\} \\ \{p,q\} & \{p,r\} & \{p,q,r\} \\ \{p,r\} & \{p\} & \{p,q\} \\ \{p,q,r\} & \{p,r\} & \{p,q,r\} \end{array}$$

状態は4個で、$r$ を含む $\{p,r\}$ と $\{p,q,r\}$ が受理状態である。DFA の状態は、直前の2文字（$00, 01, 10, 11$）を覚えていることに対応する。

検算：

長さ0〜10のすべての文字列で、この DFA の受理と「長さ2以上で後ろから2文字目が1」が一致する。後ろから $k$ 文字目が1の言語では、NFA は $k + 1$ 状態、最小 DFA は $2^k$ 状態になる。

### 計算例：正規表現と DFA の対応

$\Sigma = \{0,1\}$ で、$01$ で終わる文字列の言語を正規表現と DFA で表せ。

解答：

正規表現は $(0 + 1)^*01$。DFA は「末尾がどこまで $01$ に一致しているか」を状態にする。状態 $A$（一致なし、初期）、$B$（末尾が $0$）、$C$（末尾が $01$、受理）として

$$\delta(A,0) = B,\ \delta(A,1) = A,\ \delta(B,0) = B,\ \delta(B,1) = C,\ \delta(C,0) = B,\ \delta(C,1) = A$$

検算：

長さ0〜10の全文字列で、この DFA と正規表現の受理が一致する。$\varepsilon$、$0$、$01$ は互いに別の同値類である（$\varepsilon$ と $0$ は後ろに $1$ を付けると、$01$ と他の2つは何も付けないと受理が分かれる）。マイヒル・ネローデの定理から3状態より少なくはできない。

## 反復補題で正規でないことを示す

### 定理・法則：正規言語の反復補題

条件：

$L$ は正規言語。

主張：

ある整数 $p \ge 1$ が存在して、$|w| \ge p$ を満たす任意の $w \in L$ は、次の3条件を満たす $w = xyz$ に分解できる。

- $|xy| \le p$
- $|y| \ge 1$
- すべての $i \ge 0$ で $xy^iz \in L$

要点：

$p$ を DFA の状態数にとると、長さ $p$ 以上の文字列を読む途中で同じ状態を2回通り、その間の部分が $y$ になる。逆は成り立たない。反復補題の条件を満たしても正規とは限らないので、この補題は正規でないことの証明にだけ使う。

### 計算例：$\{a^n b^n\}$ が正規でないことの証明

$L = \{a^n b^n \mid n \ge 0\}$ が正規言語でないことを示せ。

解答：

$L$ が正規だと仮定し、反復補題の定数を $p$ とする。$w = a^p b^p \in L$ は $|w| = 2p \ge p$ を満たす。任意の分解 $w = xyz$（$|xy| \le p$、$|y| \ge 1$）で、$xy$ は先頭 $p$ 文字に含まれるので $y = a^k$（$1 \le k \le p$）である。$i = 2$ とすると $xy^2z = a^{p+k}b^p$ で、$a$ と $b$ の個数が異なるから $L$ に入らない。これは補題に反するので $L$ は正規でない。

検算：

$p = 1, \dots, 7$ で $a^pb^p$ のすべての分解を列挙し、$xy^2z \notin L$ を確かめた。$L$ は文脈自由言語で、文法 $S \to aSb \mid \varepsilon$ で生成できる。

反復補題による証明は「任意の $p$ に対して、ある $w$ を選び、任意の分解に対して、ある $i$ で $L$ から外れる」という順の論理になる。$w$ と $i$ は自分で選べるが、$p$ と分解は選べない。閉包性と組み合わせる方法もある。たとえば $L' = \{w \mid w \text{ の } a \text{ と } b \text{ の個数が等しい}\}$ が正規なら、$L' \cap a^*b^* = \{a^nb^n\}$ も正規になって矛盾する。

## 答案でよくある誤り

1. 反復補題で分解 $xyz$ を自分に都合よく1つ選ぶ。分解は「任意の」分解で、$|xy| \le p$ と $|y| \ge 1$ を満たすすべての場合で $L$ から外れることを示す。
2. 反復補題の条件を満たすことを確かめて「正規である」と結論する。補題は必要条件なので、正規であることは DFA・NFA・正規表現を作るか閉包性で示す。
3. NFA の受理状態と非受理状態を入れ替えて補集合の NFA とする。非決定性のままでは補集合にならないので、部分集合構成で完全な DFA にしてから入れ替える。
4. DFA で、ある状態から出る遷移が足りないまま完成とする。DFA は全状態・全記号に遷移が1つずつ必要で、行き先がない場合は抜け出せない非受理状態（死に状態）を加える。
5. 部分集合構成で $\varepsilon$ 閉包をとり忘れる。初期状態にも、各遷移の行き先にも $E(\cdot)$ を適用する。
6. $(a+b)^*$ と $a^* + b^*$ を同じ言語とする。$ab$ は前者に入るが後者には入らない。

## オートマトンと正規言語が出た院試の過去問

### [オートマトン理論](https://inshihub.com/exam-themes/automata-theory)（11大学・24問）

- [名古屋工業大学 情報工学系 2026年度 第1問](https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering/2026#problem-1): 計算機ソフトウェア
- [早稲田大学大学院 情報理工・情報通信専攻 専門科目 2026年度 第1問](https://inshihub.com/exam-solutions/waseda-university/graduate-school-of-fundamental-science-and-engineering/computer-science-and-communications-engineering/2026#problem-1): 情報基礎
- [東京大学 専門科目（コンピュータ科学） 2026年度 第1問](https://inshihub.com/exam-solutions/tokyo-university/information-science/computer-science/2026#problem-1): 形式言語とオートマトン
- [静岡大学大学院 情報科学 2026年度 第1問](https://inshihub.com/exam-solutions/shizuoka-university/graduate-school-of-integrated-science-and-technology/computer-science/2026#problem-1): オートマトンと行列式
- [九州工業大学大学院 専門科目（知能情報工学） 2025年度 第1問](https://inshihub.com/exam-solutions/kyushu-institute-of-technology/graduate-school-of-computer-science-and-systems-engineering/intelligent-informatics/2025#problem-1): 離散数学系科目群
- [北海道大学大学院 情報科学専攻 情報理工学コース 専門科目 2025年度 第2問](https://inshihub.com/exam-solutions/hokkaido-university/graduate-school-of-information-science-and-technology/computer-science-and-information-technology/2025#problem-2): 情報数学

解答まで無料で読める演習問題:

- [早稲田大学大学院 情報理工・情報通信専攻 専門科目 2026年度 第1問](https://inshihub.com/exam-solutions/waseda-university/graduate-school-of-fundamental-science-and-engineering/computer-science-and-communications-engineering/2026#problem-1): 情報基礎
- [東京大学 専門科目（コンピュータ科学） 2026年度 第1問](https://inshihub.com/exam-solutions/tokyo-university/information-science/computer-science/2026#problem-1): 形式言語とオートマトン
- [静岡大学大学院 情報科学 2026年度 第1問](https://inshihub.com/exam-solutions/shizuoka-university/graduate-school-of-integrated-science-and-technology/computer-science/2026#problem-1): オートマトンと行列式
- [九州工業大学大学院 専門科目（知能情報工学） 2025年度 第1問](https://inshihub.com/exam-solutions/kyushu-institute-of-technology/graduate-school-of-computer-science-and-systems-engineering/intelligent-informatics/2025#problem-1): 離散数学系科目群

### [正規表現・形式言語](https://inshihub.com/exam-themes/regular-expressions)（10大学・33問）

- [九州大学大学院 専門科目（情報系4分野） 2026年度 第2問](https://inshihub.com/exam-solutions/kyushu-university/graduate-school-of-information-science-and-electrical-engineering/information-science-specialized-subjects/2026#problem-2): オートマトンと言語
- [北海道大学大学院 情報科学専攻 情報理工学コース 専門科目 2026年度 第2問](https://inshihub.com/exam-solutions/hokkaido-university/graduate-school-of-information-science-and-technology/computer-science-and-information-technology/2026#problem-2): 情報数学
- [名古屋工業大学 情報工学系 2026年度 第1問](https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering/2026#problem-1): 計算機ソフトウェア
- [東京大学 専門科目（コンピュータ科学） 2026年度 第1問](https://inshihub.com/exam-solutions/tokyo-university/information-science/computer-science/2026#problem-1): 形式言語とオートマトン
- [京都大学 知能情報学コース 2025年度 第9問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/intelligence-science-and-technology/2025#problem-9): S-5 形式言語理論
- [京都大学 通信情報システムコース 2025年度 第9問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering/2025#problem-9): B-5 オートマトンと言語

解答まで無料で読める演習問題:

- [東京大学 専門科目（コンピュータ科学） 2026年度 第1問](https://inshihub.com/exam-solutions/tokyo-university/information-science/computer-science/2026#problem-1): 形式言語とオートマトン
- [東京大学 専門科目（コンピュータ科学） 2025年度 第1問](https://inshihub.com/exam-solutions/tokyo-university/information-science/computer-science/2025#problem-1): 形式言語とオートマトン
- [名古屋工業大学 情報工学系 2024年度 第1問](https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering/2024#problem-1): 計算機ソフトウェア
- [早稲田大学大学院 情報理工・情報通信専攻 専門科目 2024年度 第1問](https://inshihub.com/exam-solutions/waseda-university/graduate-school-of-fundamental-science-and-engineering/computer-science-and-communications-engineering/2024#problem-1): 情報基礎