The proof of language $F = \{ww\mid w ∈ \{0,1\}^*\}$ is not a regular language using pumping lemma most of the solutions i found uses the string $0^p10^p1$. I understand the proof using that. But in Michael Sipser's Introduction to the Theory of Computation book he mention that using $0^p0^p$ string will fails to proof $F$ is not a regular language. But from what I understood if we take the string as $0^{p-r}0^{r}0^{p}$ where $p$ is the pumping length when $r= 0$ the string that generate is $0^{p}10^p$. So this is clearly a string that not generated by this language. By using this we can prove $F$ is not a regular language. Is this correct?



No it's not, because $0^r$ means "$0$ repeated $r$ times". The operation that is repeated is concatenation and not multiplication. In particular, $0^0$ is the empty word $\varepsilon$ (because it is the neutral element of concatenation), and certainly not $1$.

  • $\begingroup$ hi, i'm not sure i understood it well.In maths zero to the power of any number will be 1.So why this is different than this? $\endgroup$ – Learner Jun 11 '13 at 3:52
  • $\begingroup$ Here the objects you manipulate are not number but strings. The power of a string is the same string concatenate with itself, for instance $0^3$ is $000$, which is not equal to $0$. To avoid confusions, people usually use $a$ and $b$ instead of $0$ and $1$. $\endgroup$ – Denis Jun 11 '13 at 11:59

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.