This is a question from a past exam.

Consider the language $F = \{w | w \in 0^{*}1^{*}\}$ that is kown to be regular.

a) Show that if string $w$ is chosen to be $0^p1^p$, that is a member of $F$, $F$ cannot be pumped.

b) However, we know that $F$ is regular. Why does the solution to the above question not contradict the pumping lemma?

Well, when I first read this questions, I thought (to answer b) about a possible wrong usage of the reciprocal: The pumping lema states that if a language is regular, then certain properties are satisfied, but we can say nothing about the reciprocal. However, it seems that it's not the case.

a) doesn't make sense for me. If the language is regular, then any sufficiently long string in the language can be pumped (by the way, I'm also a little confused by the terminology: I thought we usually use the verb "pump" referring to strings, not languages). I assume that $p$ is the pumping length.

What's my mistake?


Edit: My first answer wasn't very useful indeed. After thinking about it a lot, I think I now understand what the exam question means: We can pump any word from $F$, but we can't pump the language from that word, meaning we can't recreate the language from one specific word. I'll now show that we can pump $0^p 1^p$:

Let $F=\{w | w \in 0^{*} 1^{*}\}$ be regular. Then there is a $n$ such that all words $z \in L$ with $|z| \geq n$ can be decomposed to $z = uvw$ such that

  1. $uv \leq n$
  2. $|v|\geq 1$
  3. $\forall i \in \mathbb{N}_0:$ $uv^iw \in L$

Choose $z = 0^n 1^n \in F$. Because of (2) and (1), $v$ is not empty and $uv$ has only got $0$'s (since $|uvw| = |0^n 1^n | = 2n$) With (3)

$$ uv^i w = 0^{n-|v|} 0^{i|v|} 1^n = 0^{n+(i-1)|v|}1^{n}$$

has to be element of the language $L$ for all $i \in \mathbb{N}$, which it is. So you can pump $z = 0^n 1^n$.

What the exam question means (I guess!) is that you can pump the word, but you can't reconstruct the language from this word. Because "pumped" the word looks like

$$ 0^{n+(i-1)|v|}1^{n}$$

which always contains $(i-1)|v|$-times more $0$'s than $1$'s. So you can't pump the whole language using the decomposition of this specific word, since for example

$0^k 1^l \in L$, for $l > k$, but for $i \notin \{0,1\}$: $0^k 1^l \neq 0^{n+(i-1)|v|}1^{n}$ $\forall n$.

The answer to (b) is that this doesn't contradict the Pumping lemma since it doesn't require you being able to pump the whole language with one specific word.

  • $\begingroup$ Hi. I'm a little bit confused. I think pumping (ap bp) means that we can divide it in three parts, each one satisfying he properties of the theorem. However, it seems to me that it doesn't mean that we need to know the number of a's and b's. The theorem states that, if L is a regular language, then all strings with length > p can be pumped (i.e., can be divided in a such way that the three properties are satisfied). If this particular string w could not be pumped, I think we would have a contradiction. $\endgroup$ – user35477 Oct 7 '14 at 16:59
  • $\begingroup$ @user35477 You are correct. I thought about the exam question again and found in a text book that $0^n 1^n$ can indeed be pumped. So I edited the answer - it should make more sense now I hope. $\endgroup$ – TheWaveLad Oct 8 '14 at 7:39

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.