# Prove that a language B is regular

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.

-
I just built the DFA and thus proved that B is regular. Thanks so much for confirming my initial assumption. Thanks a lot! –  Dave Oct 2 '12 at 3:22
@Dave: You’re welcome! –  Brian M. Scott Oct 2 '12 at 3:24
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) –  Dave Oct 2 '12 at 3:50
@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. –  Brian M. Scott Oct 2 '12 at 3:52
@TheNotMe: That’s even better. You’re welcome! –  Brian M. Scott Nov 30 '13 at 17:25
show 4 more comments

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

-