91Ó°ÊÓ

A language is regular if it is recognized by a DFA. So, construct a DFA to keep track the remainder of the input when it is divided by n .

Construction of DFA is as follows:

Assume the value of n as 3.

To determine whether a binary number is a multiple of 3, it is necessary to find its remainder modulo 3.

If it ends up with remainder zero, then accept.

Otherwise reject.

Every time read a digit; the preceding string is shifted left one position thereby doubling its value x.

If the current digit is 0, them the new value is $2x  (\mathrm{mod}  3)$.

If the current digit is 1, them the new value is $2x+ 1 (\mathrm{mod}  3)$.

The DFA for the above example is as follows:

Similarly, for $n=5$the DFA is as follows:

The other case can be proved similarly.

For example:

$\begin{array}{rcl}{C}_6& =& C_{3}0\\ C_{12}& =& C_{6}00\\ C_{15}& =& C_3âˆ\copyright C_5...\end{array}$

Thus $M=\left(\left\{q_0,q_1,.......q_n\right\},\left\{0,1\right\},\mathrm{δ},q_0,\left\{q_0\right\}\right)$,

Since M recognizes language $C_n$, it is proved that $C_n$is regular