2進数に絡んだ問題つぎに、0,1で与えられる文字列を2進数と考えるタイプの問題も練習していきましょう。正則か正則でないかを判定し、正則であれば最小状態決定性オートマトンを書きなさい。正則でない場合の証明は不要。\right\}\]解説4(1)10進数に直したときに4の倍数となるようなものを順番に書いていけば法則がわかるかもしれないので書いていこう。......と書いてくと、00で終わるような文字列は必ず4の倍数となることがわかるだろう。00で終わるような文字列は下のような有限オートマトンで記述することができるので正則である。(2)3の倍数は4の倍数ような単純な規則とはならない。正則ではないと思ったそこのあなた...どんな数(範囲は無限大)でも3で割ったあまりは0か1か2の3通りしかありませんよね。0,1,2の3通りは当然有限個なので有限オートマトンを書くことができ、正則なのです。いうことで、とある2進数を3で割ったあまりが0のとき、1のとき、2のときの3つに場合分けをする。それぞれの状態(あまりが0,1,2それぞれの2進数の状態)に0を加えたとき、1を加えたときに3で割ったあまりがどうなるかを考える。ある2進数の右端に0を加えると、その2進数の値は2倍に、1を加えると2倍+1されることに注意すると以下のように表せる*2。