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

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

とし、初期状態 $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の倍数」が一致することを実装で確かめた。

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

状態は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$ 状態になる。

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

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

$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$ で生成できる。