Proving that $\mathscr L=\{0^n \big|\text{n is the square of a natural number }\}$ is non regular using the pumping lemma

1.1k Views Asked by At

I need to prove that the language $\mathscr L=\{0^n \big|\text{n is the square of a natural number}\}$ is non regular using the pumping lemma

My try:

$\mathscr L=\{\overbrace{\epsilon}^{0^2},\overbrace{0}^{1^2},\overbrace{0000}^{2^2},\overbrace{000000000}^{3^2},\overbrace{0000000000000000}^{4^2},\dots\}$

Suppose that $\mathscr L$ is regular so $\exists$ a word '$x$' with length of at least $n$

$|x|\geq n $ such that

$(1)\,\,\,|uv|\leq n$

$(2)\,\,\,|v|\geq 1$

$(3)\,\,\,uv^iw \in \mathscr L$

Now, let as choose the word $\color{blue}{x=0^{n^2}}$ $|x|\geq n$ so we can use $(1)-(3)$

$x=\underbrace{000000\dots}_{n^2\text{ times}}$

$x=uv0^kw=\underbrace{uv0^k}_{\text{n zeros }}\overbrace{w}^{n^2-n\text{ zeros }}$

Let as choose $\color{blue}{i=??}$

I'm difficult choosing the word '$\color{blue}x$' and choosing $\color{blue}i$ to come to contradiction with the lemma

1

There are 1 best solutions below

0
On BEST ANSWER

Start with $x=0^{n^2}$, as you did. Then we can decompose $x$ as $x=uvw$ in such a way that $|uv|\le n$, $|v|\ge 1$, and $uv^kw\in\mathscr{L}$ for all $k\ge 0$. Clearly there are $r\ge 0$ and $s\ge 1$ such that $u=0^r$, $v=0^s$, and $r+s\le n$. Thus, for each $k\ge 0$ we have

$$uv^kw=0^r0^{ks}0^{n^2-r-s}=0^{ks}0^{n^2-s}=0^{n^2+(k-1)s}\;,$$

and we need to show that there is a $k\ge 0$ such that $n^2+(k-1)s$ is not a perfect square.

For $k\ge 0$ let $a_k=n^2+(k-1)s$; the sequence $\langle a_k:k\ge 0\rangle$ is an arithmetic sequence with constant difference $s$, meaning that $a_{k+1}-a_k=s$ for all $k$. On the other hand, the gaps between consecutive squares get bigger and bigger: $(m+1)^2-m^2=2m+1$. Thus, when $k$ is large enough the terms $a_k$ and $a_{k+1}$ are too close together for both to be squares.

Specifically, if $a_k=m^2$ for some $k$ and $m$, and $s<2m+1$, then $a_{k+1}<(m+1)^2$. Thus, if we choose any $m$ such that $2m+1>s$, and then choose $k$ so that $a_k\ge m^2$, it follows that $a_k$ and $a_{k+1}$ cannot both be squares.