オートマトン・形式言語の問題

拡張遷移関数 ${\delta }^{\ast }:Q\times {\Sigma }^{\ast }\to Q$ を ${\delta }^{\ast }(q,\epsilon )=q$、${\delta }^{\ast }(q,u\sigma )=\delta ({\delta }^{\ast }(q,u),\sigma )$（$u\in {\Sigma }^{\ast }$, $\sigma \in \Sigma$）で定める。文字列 $w$ が受理されるのは ${\delta }^{\ast }(q_0,w)=q_0$ のときである。

0 以上の整数 $n$ に対し、長さ $n$ の文字列 $w$ で ${\delta }^{\ast }(q_0,w)=q_0,q_1,q_2$ となるものの個数をそれぞれ $x_n,y_n,z_n$ とおく。定義から $A_n=x_n$ である。

ステップ 1（個数の和）　$M$ は決定性なので、各文字列 $w$ に対して ${\delta }^{\ast }(q_0,w)$ は $Q$ のちょうど 1 つの状態に定まる。よって長さ $n$ の文字列全体（$2^n$ 個）は、終わりの状態によって 3 つの組に重なりなく分けられ、
$$x_n+y_n+z_n=2^n(1)$$
が成り立つ。

ステップ 2（漸化式）　長さ $n+1$ の文字列 $w$ は、長さ $n$ の文字列 $u$ と文字 $\sigma \in \Sigma$ を用いて $w=u\sigma$ とただ 1 通りに書ける。逆に任意の $(u,\sigma )$ から長さ $n+1$ の文字列 $u\sigma$ が得られるので、$w\leftrightarrow (u,\sigma )$ は全単射である。このとき ${\delta }^{\ast }(q_0,w)=\delta ({\delta }^{\ast }(q_0,u),\sigma )$ である。

表から、$\delta (q,\sigma )=q_0$ となる組 $(q,\sigma )$ は $(q_1,b)$ と $(q_2,a)$ のちょうど 2 つである（$\delta (q_0,a)=q_1$, $\delta (q_0,b)=q_2$ なので $q=q_0$ からは $q_0$ に移らない）。したがって ${\delta }^{\ast }(q_0,w)=q_0$ となるのは、「${\delta }^{\ast }(q_0,u)=q_1$ かつ $\sigma =b$」または「${\delta }^{\ast }(q_0,u)=q_2$ かつ $\sigma =a$」のときであり、この 2 つの場合は $u$ の終わりの状態が異なるので重ならない。全単射性より
$$x_{n+1}=y_n+z_n(2)$$
を得る。$(1)$ と $(2)$ から
$$x_{n+1}=2^n-x_n(3)$$
がすべての 0 以上の整数 $n$ で成り立つ。

ステップ 3（数学的帰納法）　命題 $P(n)$：「$x_n=\frac{2^n+2(-1{)}^n}{3}$」がすべての 0 以上の整数 $n$ で成り立つことを、$n$ についての帰納法で示す。

(i) $n=0$ のとき：長さ $0$ の文字列は $\epsilon$ のみで、${\delta }^{\ast }(q_0,\epsilon )=q_0$ なので受理される。よって $x_0=1$。一方 $\frac{2^0+2(-1{)}^0}{3}=\frac{3}{3}=1$ なので $P(0)$ は成り立つ。

(ii) ある 0 以上の整数 $n$ で $P(n)$ が成り立つと仮定する。$(3)$ と仮定より
$$x_{n+1}=2^n-\frac{2^n+2(-1{)}^n}{3}=\frac{3\cdot 2^n-2^n-2(-1{)}^n}{3}=\frac{2^{n+1}-2(-1{)}^n}{3}=\frac{2^{n+1}+2(-1{)}^{n+1}}{3}$$
となり、$P(n+1)$ が成り立つ。

(i), (ii) より、すべての 0 以上の整数 $n$ について $P(n)$ が成り立つ。

以上より、すべての 0 以上の整数 $n$ について $A_n=x_n=\frac{2^n+2(-1{)}^n}{3}$ である。（確認：$n=1$ では $a,b$ はそれぞれ $q_1,q_2$ で終わるので $A_1=0=\frac{2-2}{3}$、$n=2$ では $ab,ba$ のみ受理されるので $A_2=2=\frac{4+2}{3}$ となり、式と一致する。）$■$