Pumping lemma on {a^n | n=3^k} — help finishing the proof [duplicate]

Question

I am working on a pumping lemma question and trying to prove that the following is not regular, but I can't finish the proof, if someone can help me it will be great.

So I am given this language: $L = \{ a^n | n = 3^k , k≥0 \}$ . Ok. I choose $w = a^{3^m}$. I know for sure that $y = a^t$ ($y$ must be any number or $a$'s), where $t≥1$. $x = a^{(3^m)-t}$ and $y = a^t$. I pump twice, so $i =2$ and $xy = a^{(3^m)+t}$.

Now, is this enough to finish the proof? What is my $xyz$? and how do I prove that my $w$ is not in the language? Thank you so much for whoever decide to help me out!

Answer 1

It is not enough. Also note that you didn't define $x$ correctly, and forgot $z$. I would define: $$x = a^s$$ $$y = a^t$$ $$z = a^{3^m - s -t}$$ such that $s + t <= m$ and $t >= 1$ (hence $1 <= t <= m$)

You need to show that for $i=2$, you get something that is not in L (meaning, there is no $k$ such that $x(y^2)z = a^{3^k}$ ).

Let's look at $x(y^2)z = a^{3^m+t}$. Its length is $3^m + t$.

Using the fact that for every $i, i < 3^i$, We get: $3^m < 3^m + 1 \le |x(y^2)z| = 3^m + t \le 3^m + m < 3^m + 3^m = 3^{m+1}$

We see that the length of $xy^2z$ isn't in the form of $3^n$ (it's something between $3^m$ to $3^{m+1}$, hence it is not in L. Contradiction to the pumping lemma.