Question

Let ${\mathit{C}}_{\mathbf{n}}\mathbf{}\mathbf{=}\mathbf{\left\{}\mathit{x}\mathbf{\right|}\mathit{x}$is a binary number that is a multiple of n}. Show that for each $\mathit{n}\mathbf{⩾}\mathbf{1}$, the language $\mathit{C}\mathit{n}$is regular

Short answer

It is proved that $C_n$ is regular.

Step-by-step solution

To Show that for each n⩾1 the language is regular

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 .

To Construct a DFA

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.

To Give Some examples for DFS

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\cap C_5...\end{array}$

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

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