0

$L=\{0^n\#0^{2n}\mid n\ge 0\}$
Show that this language is iiregular. And now: Let $p$ will be length of pumping lemma. Given $w=0^p\#0^{2p}=xyz\in L$ such that. Becaues of the fact that $|xy|\le p$ we conclude that $y$ contains only $0s$. So let's pump up. Then $xy^2z=0^{p+k}\#0^{2p}$. Because $2(p+k)\neq 2p$ we conclude a condruction. So $L$ is irregular.

Is it ok ?

Michael Hardy
  • 1
user220688
  • 509

1 Answers1

1

It’s almost right, but not quite. We know that $y=0^r$ for some $r\ge 1$, so

$$xy^kz=0^{p+(k-1)r}\#0^{2p}\;,$$

not $0^{p+k}\#0^{2p}$: the length of $y$ need not be $1$. But we’re still okay, because $2\big(p+(k-1)r\big)=2p$ if and only if $k=1$, so the pumped word is not in the language when $k\ne 1$.

Brian M. Scott
  • 616,228
  • Ok, I understand. But in my book there was considered three cases: $(1)#\in x(2)#\in y (3)#\in z$ Why ? (It was also said that $xy\le p$) – user220688 Apr 18 '15 at 18:02
  • @user220688: One of the assertions of the pumping lemma is that the word can be decomposed into $xyz$ in such a way that $|xy|\le p$. (The others are that $|y|\ge 1$, and that $xy^kz$ is in the language for each $k\ge 0$.) There’s no need for that division into cases if you start with the word $0^p#0^{2p}$, as you did: the pumping lemma says that it can be decomposed as $xyz$ in such a way that $|xy|\le p$, which ensures that the $#$ is in $z$. Either they started with a word $0^n#0^{2n}$, where $3n+1\ge p$, or they added an unnecessary complication. – Brian M. Scott Apr 18 '15 at 18:08
  • @user220688: You’re very welcome. – Brian M. Scott Apr 19 '15 at 18:34