proof with using pumping lemma

37 Views Asked by At

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

1

There are 1 best solutions below

3
On BEST ANSWER

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