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

Question

Let $B_{n} = \{a^{k}| \text{$k$ is a multiple of $n$}\}.$ Show that for each $n\geq 1,$ the language $B_{n}$ is regular$.$

Answer 1

Method 1:

Each language $B_n$ has a specific value of n, so n is not a free variable. Although k is a free variable, the number of states is bounded by n, and not k

Regular languages can be infinite but must be described using finitely-many states.  For an FA to generate an infinite set of strings, what must there be between some states? A loop. This leads to the famous pumping lemma.

 The Pumping Lemma states that all regular languages have a special pumping property. If a language does not have the pumping property, then it is not regular.  So one can use the Pumping Lemma to prove that a given language is not regular.

 

Method 2: Draw DFA for the language and verify it accept all the strings generated by language and does not accept the strings which are not generated by language. 

Answer 2

n=1,  $B_{1}$=$a^k$      

n=2,  $B_{2}$=$a^{2k}$

n=3,  $B_{3}$=$a^{3k}$
_____________________

$B_{n}$=$a^{nk}$

using Pumping Lemma we can prove $B_{1}$, $B_{2}$, $B_{3}$............... ,$B_{n}$ are regular