# Prove that the language $\{ww \mid w \in \{a,b\}^*\}$ is not FA (Finite Automata) recognisable.

Hint: Assume that $|xy| \le k$ in the pumping lemma.

I have no idea where to begin for this. Any help would be much appreciated.

-
What is a "FA" ?, what is "E" ? – Belgi Oct 17 '12 at 10:33
Also, It seems that you should use the pumping lemma, what words did you try ? – Belgi Oct 17 '12 at 10:35
FA = Finite Automata and E is supposed to be epsilon. Sorry, I didn't know how to format it here. – zeqof Oct 17 '12 at 10:52
That is not an epsilon. you meant $\in$. Again, what words have you tried ? – Belgi Oct 17 '12 at 11:11
@Belgi: I think that the OP wants a tag that indicates his difficulty writing the proof, so I’ve substituted that tag. – Brian M. Scott Oct 17 '12 at 11:28

Suppose that $L$ is regular. The pumping lemma for regular languages then says that there is a positive integer $p$ such that whenever $w\in L$ and $|w|\ge p$, $w$ can be written as a concatenation $xyz$ such that $|y|\ge 1$, $|xy|\le p$, and $xy^kz\in L$ for all integers $k\ge 0$. To show that $L$ is not regular, you need only find a word $w\in L$ that cannot be written as such a concatenation.

Let $w=ab^pab^p$; clearly $w\in L$ and $|w|=2p+2\ge p$. Suppose that $w=xyz$, where $|y|\ge 1$, $|xy|\le p$, and $xy^kz\in L$ for all integers $k\ge 0$. Then $xy=ab^n$ for some $n\le p-1$ (why?), so either $x$ is empty and $y=ab^n$, or $y=b^m$ for some $m\ge 1$. In either case, explain why $xz=xy^0z\notin L$, contradicting the hypothesis that $xy^kz\in L$ for all integers $k\ge 0$. Conclude that this word $w$ cannot be decomposed as in the pumping lemma and hence that $L$ cannot be regular.

-
Thank you for the clear explanation. – zeqof Oct 17 '12 at 22:29
@zeqof: You’re very welcome. – Brian M. Scott Oct 18 '12 at 0:22
@BrianM.Scott How to show that this language is Context sensitive? – Rishi Feb 13 '14 at 16:40

It's also possible — and perhaps simpler — to prove this directly using the pigeonhole principle without invoking the pumping lemma.

Namely, assume that the language $L = \{ww \,|\, w \in \{a,b\}^*\}$ is recognized by a finite state automaton with $n$ states, and consider the set $W = \{a,b\}^k \subset \{a,b\}^*$ of words of length $k$, where $2^k > n$.

By the pigeonhole principle, since $|W| = 2^k > n$, there must be two distinct words $w,w' \in W$ such that, after reading the word $w$, the automaton is in the same state as after reading $w'$. But this means that, since the automaton accepts $ww \in L$, it must also accept $w'w \notin L$, which leads to a contradiction.

-
Thanks. That is a lot simpler. But since the hint mentions the pumping lemma specifically, I'm going with that approach. Thanks for your method though. It will help with my revision. – zeqof Oct 17 '12 at 22:28
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}