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

DFA が文字列 $w$ を受理するのは、初期状態 $q_0$ から $w$ を左から 1 文字ずつ読んで遷移表に従って状態をたどり、最後の状態 $\hat{\delta }(q_0,w)$ が受理状態 $q_2$ になるときです。各文字列についてたどります。

$(1)10$：
$$q_0\stackrel{1}{\to }{q}_1\stackrel{0}{\to }{q}_2$$
最後の状態は $q_2$ なので受理されます。

$(2)110$：
$$q_0\stackrel{1}{\to }{q}_1\stackrel{1}{\to }{q}_0\stackrel{0}{\to }{q}_0$$
最後の状態は $q_0$ なので受理されません。

$(3)101$：
$$q_0\stackrel{1}{\to }{q}_1\stackrel{0}{\to }{q}_2\stackrel{1}{\to }{q}_2$$
最後の状態は $q_2$ なので受理されます。

$(4)0111$：
$$q_0\stackrel{0}{\to }{q}_0\stackrel{1}{\to }{q}_1\stackrel{1}{\to }{q}_0\stackrel{1}{\to }{q}_1$$
最後の状態は $q_1$ なので受理されません。

$(5)1011$：
$$q_0\stackrel{1}{\to }{q}_1\stackrel{0}{\to }{q}_2\stackrel{1}{\to }{q}_2\stackrel{1}{\to }{q}_2$$
最後の状態は $q_2$ なので受理されます。

よって、受理される文字列の番号の集合は $\{1,3,5\}$ です。

（参考：この $M$ は、文字列を 2 進数とみたときの値を $3$ で割った余りを状態 $q_0,q_1,q_2$ で記憶していて、余りが $2$ の文字列を受理します。実際、$10_{(2)}=2$, $101_{(2)}=5$, $1011_{(2)}=11$ はどれも $3$ で割ると $2$ 余ります。）

各文字列について q0 から遷移をたどる。(1) 10: q0 -1-> q1 -0-> q2、受理。(2) 110: q0 -1-> q1 -1-> q0 -0-> q0、拒否。(3) 101: q0 -1-> q1 -0-> q2 -1-> q2、受理。(4) 0111: q0 -0-> q0 -1-> q1 -1-> q0 -1-> q1、拒否。(5) 1011: q0 -1-> q1 -0-> q2 -1-> q2 -1-> q2、受理。よって受理されるのは (1), (3), (5)。