Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

closed as off-topic by Sanath K. Devalapurkar, vonbrand, mookid, Sami Ben Romdhane, mathematics2x2life Apr 4 '14 at 4:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Sanath K. Devalapurkar, mookid, Community, mathematics2x2life
If this question can be reworded to fit the rules in the help center, please edit the question.

Hi! Welcome to M.SE! Could you show some work that you've done regarding this problem? It helps us analyze where you need help. – Sanath K. Devalapurkar Apr 3 '14 at 22:53
This has extensive discussion over at CsSE. – vonbrand Apr 3 '14 at 22:57
This question appears to be off-topic, it should go to CsSE – vonbrand Apr 3 '14 at 22:58
Pumping Lemma! As suggested below. – InsigMath Apr 3 '14 at 23:03
@vonbrand: Automata theory is completely on topic here. – Henning Makholm Apr 3 '14 at 23:06

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.

share|cite|improve this answer
+1, this is the intuition behind the Myhill-Nerode theorem. Much easier to apply than the pumping lemma. – Henning Makholm Apr 3 '14 at 23:06

Hint One usually derives a contradiction via the Pumping Lemma.

share|cite|improve this answer

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?

share|cite|improve this answer

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.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.