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

長さ $k$ の文字列を読み終えたときに状態が $p,q,r$ にあるような文字列の個数を、それぞれ $P_k,Q_k,R_k$ とおく。初期状態は $p$ なので
$$P_0=1,Q_0=0,R_0=0$$
である。

遷移表から、1 文字読んだ後に各状態へ入る遷移を集めると
- $p$ に入るのは $\delta (q,a)=p$ と $\delta (r,b)=p$
- $q$ に入るのは $\delta (p,a)=q$ と $\delta (q,b)=q$
- $r$ に入るのは $\delta (p,b)=r$ と $\delta (r,a)=r$

である。$M$ は決定性なので、各文字列はただ 1 つの状態に行き着く。よって
$$P_{k+1}=Q_k+R_k,Q_{k+1}=P_k+Q_k,R_{k+1}=P_k+R_k$$
が成り立つ。これを順に計算すると次のようになる。

（検算: 各 $k$ で $P_k+Q_k+R_k=2^k$ になっている。たとえば $k=10$ で $342+341+341=1024=2^{10}$。）

受理状態は $p$ だけなので、求める個数は $P_{10}=342$ である。

（補足: $Q_k=R_k$ と $P_k+Q_k+R_k=2^k$ から $P_{k+1}=2Q_k=2^k-P_k$ となり、これを解くと $P_k=\frac{2^k+2(-1{)}^k}{3}$ が得られる。$k=10$ を代入すると $\frac{1024+2}{3}=342$ で一致する。）

答え: $342$

長さ $n$ の文字列で、$p$ から出発して状態 $p,q,r$ に到達するものの個数をそれぞれ $P_n,Q_n,R_n$ とする。表より $p$ へ入る遷移は $q\stackrel{a}{\to }p$ と $r\stackrel{b}{\to }p$、$q$ へ入る遷移は $p\stackrel{a}{\to }q$ と $q\stackrel{b}{\to }q$、$r$ へ入る遷移は $p\stackrel{b}{\to }r$ と $r\stackrel{a}{\to }r$ である。よって
$$P_{n+1}=Q_n+R_n,Q_{n+1}=P_n+Q_n,R_{n+1}=P_n+R_n,$$
初期値 $(P_0,Q_0,R_0)=(1,0,0)$。

受理状態は $p$ のみなので答えは $P_{10}=342$。

検算: 各 $n$ で $P_n+Q_n+R_n=2^n$（$n=10$ で $342+341+341=1024$）。また $Q_n=R_n$ より $P_{n+1}=2Q_n$, $Q_{n+1}=P_n+Q_n$ から $P_n=\frac{2^n+2(-1{)}^n}{3}$ となり、$n=10$ で $\frac{1024+2}{3}=342$ で一致する。