Prove this language is not regular

Question

How do I prove that this language = {1^k | k is a perfect square} is not regular by showing that no DFA can accept the language?

Answer 1

Hint One usually derives a contradiction via the Pumping Lemma.

Answer 2

Suppose (for contradiction) that the language $L$ is recognized by a DFA $M=(Q,Σ,δ,q_0,F)$.

You have to show that $M$ has infinitely many states and so it is not a finite automata, giving the desired contradiction.

Answer 3

Let $L$ be the given language and suppose for a contradiction that $L$ is regular. Then, by the Pumping Lemma there must exists some positive constant $p > 0$ such that any string in $L$ of length at least $p$ can be pumped. Consider the string $w = 1^{p^2} \in L$. Since $|w| = p^2 \geq p$, we can split $w$ in three parts $x,y,z$, that is, we can write $w = xyz$ such that

1. $|xy| \leq p$,
2. $|y| \neq 0$, i.e. $y \neq \epsilon$,
3. $xy^iz \in L$ for any $i \geq 0$.

Now, choose $i=2$. Then we must have that $w' = xy^2z = xyyz \in L$. Let $|y| = q$. Since $w = 1^{p^2} = xyz$, it follows that $s = 1^{p^2 + q}$. By (2), $q \neq \epsilon$ so $p^2 < p^2 + q$. Can you take it from here?

Answer 4

You can use the Myhill-Nerode theorem. Define equivalence relation on $\{1\}^*$ $$x R_L y \Leftrightarrow \forall z\in\{1\}^*, (xz\in L \leftrightarrow yz\in L)$$ The theorem states that $L$ is regular if and only if this relation produces finitely many equivalence classes, which means that there will be a minimal DFA (one state for each equivalence class) accepting the language.

But then, you can see that this relation produces countably many equivalence classes (actually, each string forms an equivalence class and you have countalbe many strings in $\{1\}^*$), so there is no possible DFA recognizing it.