Take the 2-minute tour ×
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.

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.

share|improve this question
    
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
1  
@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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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 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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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