Michael Sipser Edition 3 Exercise 1 Question 37 (Page No. 89)

Question

Let $C_{n} = \{x| x \text{ is a binary number that is a multiple of $n$}\}.$ Show that for each $n\geq1,$ the language $C_{n}$ is regular$.$

Answer 1

This Question is similar to Designing a DFA of a binary number which is divisible by n.

So that if we can draw the DFA which accepts all the elements generated by the language and does not accept the element which is not generated by the language it will prove that it is regular.

Consider the example where n=3 :

we draw the DFA for given language when n=3 as

 

Similarly, we can design the DFAs for for different values of n .

Since we are able to design the DFA it proves language is Regular.