2
$\begingroup$

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.

2 Answers 2

4

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.

  • 1
    @TheNotMe: That’s even better. You’re welcome!2013-11-30
1

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