Please help me understand the following

$L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$

To prove: The language $L$ has regular pumping property

My argumentation:

Let $p = 4 $. Let $z$ in $L$, with $z$ $\geq $ $p$. Set $u$ to $\epsilon$. Than $x$ is the first letter, and $w$ the rest.

$x$ $\neq$ $\epsilon$

For all $i$ $\geq $0$: ux^iw$ is in $L$

But if i set i to 0 the word is not in the language? And therefor does not have the regular pumping property? What am i missing? Example $0010$, after pumping $4$ $\geq $ $010$?

  • $\begingroup$ Could you please explain why I can't choose my own pumping length? $\endgroup$ – Michael Maier Mar 8 at 20:53
  • $\begingroup$ I now see what you are trying to do. You are trying to "explicitly" show that the pumping lemma holds. Then you are allowed to fix a $p$ and prove that you can "pump" all words $z$ of length $|z| \ge p$. You can (and should) also pick the decomposition of $z$ as a function of $z$. However this approach can only show that the pumping lemma holds. If you fix a value of $p$ or a particular way to chose a decomposition of $z=uxw$ and you are not able to show that $ux^iw \in L \; \forall i \ge 0$ you can't say that the language is not regular (maybe your choices were wrong)! $\endgroup$ – Steven Mar 8 at 21:20
  • $\begingroup$ My answer shows that there exists a $p$ and a decomposition that will work (since $L$ is regular), but doesn't explicitly tell you what the value of $p$ is or what the decomposition should be. This is enough to formally prove the claim you wanted to show, but perhaps it is not so satisfying. The answer of Hendrik Jan shows that you can pick $p=3$ (actually, in this case, any $p\ge1$ works, since any word in $L$ can be pumped anyway) and provides a constructive way to find the decomposition $z=xyw$ (essentially $y$ is always either the 1st or the 3rd character). Other choices might work too. $\endgroup$ – Steven Mar 8 at 21:30

I assume that you want to show that the language $L$ does satisfy the Pumping Lemma, as it indeed is regular. In words your language consists of all strings that have length at least 4 and contain two consecutive symbols that are the same. The position of a pair of equal letters letters is indicated here with $i$. (Note $i$ in general is not unique.)

So we need to explain that all strings in the language (above a certain length) can be pumped within the language. You must realize that your division into $uxw$ can actually depend on the string $a$ itself.

So if $a$ starts with a repeated letter, e.g., $a = 00\dots$, we can pump the third letter. Otherwise if the repeated pair is assumed to be not in the first position, we can then pump the first symbol and we keep the repetition in the string while pumping.

  • $\begingroup$ "So if a starts with a repeated letter, e.g., $a=00…$, we can pump the third letter." could you please explain why cant we pump the first letter? Or can a language have the regular pumping property and not be regular at the same time? $\endgroup$ – Michael Maier Mar 17 at 14:12
  • $\begingroup$ For $a = 00101$ we can't pump the first letter. For $i=0$ we would delete the first letter, and the the string would no longer contain two consecutive equal letters, and thus would not belong to $L$. $\endgroup$ – Hendrik Jan Mar 17 at 15:01
  • $\begingroup$ Yes, there are languages that are not regular, yet do satisfy the pumping lemma, but that is not the point here, I think. The language $L$ you give here is perfectly regular. A non-regular language satisfying the pumping lemma $\endgroup$ – Hendrik Jan Mar 17 at 15:06
  • $\begingroup$ to show that the negated PL applies here, the word length should still after pumping be $ \geq $ p? $\endgroup$ – Michael Maier Mar 17 at 15:35
  • $\begingroup$ @MichaelMaier After pumping the word should still belong to $L$. This particular language requires that the strings in $L$ are at least 4 letters long. $\endgroup$ – Hendrik Jan Mar 20 at 13:07

It suffices to show that the language is regular.

The language $L_1$ of all words on $\{0,1\}^*$ with at least two identical consecutive symbols is regular (since it can be described be the following regular expression: $(0\mid1)^*(00\mid11)(0\mid1)^*$).

The language $L_2$ of all words on $\{0,1\}^*$ of length at least $4$ is clearly regular (a regular expression is $(0 \mid 1)(0 \mid 1)(0 \mid 1)(0 \mid 1)(0 \mid 1)^*$).

By the closure properties of regular languages, $L = L_1 \cap L_2$ must also be regular.


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.