1

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?

thanks.

MJD
  • 65,394
  • 39
  • 298
  • 580
Learner
  • 13

1 Answers1

2

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$.

Denis
  • 6,945
  • 1
  • 21
  • 22
  • 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? – Learner Jun 11 '13 at 03:52
  • 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$. – Denis Jun 11 '13 at 11:59