here is the question I'm dealing with:

Let B = {$1^{k}$y|y $\in$ {0,1}* and y contains at least k 1s, for k $\geq$ 1}.

Show that B is a regular language.

Can I use the pumping lemma to show that this is a regular language? My intuition tells me that I can't, since I would have to find every string s that satisfies the pumping lemma.

Anyways, your suggestions are appreciated. Thank you in advance.


The pumping lemma for regular languages is only a tool for showing that a language is not regular; it cannot be used to show that a language is regular. The two most straightforward ways to demonstrate that a language is regular are (1) to write a regular grammar that generates it, and (2) to design a finite state automaton that recognizes it.

In this case, though, it pays to begin by taking a close look at just what words are in $B$. Consider a word $11x$, where $x\in\{0,1\}^*$: since we can set $k=1$, such a word is automatically in $B$, since $1x$ certainly contains at least one $1$. A word that begins with $1$ is not in $B$ if and only if it has no other $1$’s; and a word that begins with $0$ is not in $B$. Thus,

$$B=\{1x\in\{0,1\}^*:x\in\{0,1\}^*\text{ and }x\text{ has at least one }1\}\;,$$

the language corresponding to the regular expression $10^*1(0\lor 1)^*$. It’s not at all hard to design a regular grammar that generates this language, or a finite state machine that recognizes it.

  • $\begingroup$ I just built the DFA and thus proved that B is regular. Thanks so much for confirming my initial assumption. Thanks a lot! $\endgroup$ – Dave Oct 2 '12 at 3:22
  • $\begingroup$ @Dave: You’re welcome! $\endgroup$ – Brian M. Scott Oct 2 '12 at 3:24
  • $\begingroup$ wait a second.. what about string 1101. this is not accepted by B (take k=2). New B would accept it. Am I wrong? (I would be wrong if you could always pick k=1) $\endgroup$ – Dave Oct 2 '12 at 3:50
  • $\begingroup$ @Dave: The way the description of $B$ is worded allows you to choose $k$. Had it said that there is some $k\ge 1$ such that $B=\{1^ky:\text{ etc. }\}$, that would have been a different story, though not much harder. If it meant that you had to use the maximum $k$ allowed by the initial string of $1$’s, it should have said so; that would be very different. $\endgroup$ – Brian M. Scott Oct 2 '12 at 3:52
  • 1
    $\begingroup$ @TheNotMe: That’s even better. You’re welcome! $\endgroup$ – Brian M. Scott Nov 30 '13 at 17:25

You can never use (directly) the pumping lemma to show a langauge is regular since there are non-regular langauges that satisfy all the lemma properties.

In your case the langauge is very simple and you can build a finite state automata to prove regularity


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.