Is L Regular language

Question

Prove whether language $a^{(13)^n}$ is regular, or not.

Please, provide the most formal answer as it could be. My teacher is very strict.

Thanks in advance.

Answer 1

Welcome to the site! Since you're new here, I should explain that our policy is not to provide complete solutions to what are obviously homework problems, so I'll give you a skeleton proof and leave it to you to provide the meat on the bones.

Call the language $L$. Assume, to the contrary, that $L$ was regular. Then the Pumping Lemma would apply, so let $p$ be the integer of the lemma.

Now consider an integer $n$ such that $13^{n-1}< p\le13^n$. (Why is there always such an n?)

Let $s=a^{13^n}$. This string is in $L$. (Why?)

So the Pumping Lemma applies and we can write $s=xyz$ with $|xy|\le p\le 13^n$.(Why?)

And thus $|xy^2z|\le 2\cdot 13^n$. (Why?)

But $2\cdot 13^n<13^{n+1}$. (Why?)

And so $xy^2z\notin L$ (Why?) and we have a contradiction to the assumption that $L$ was regular. (Why?)