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.

I know to prove a language is regular, drawing NFA/DFA that satisfies it is a decent way. But what to do in cases like

$$ L=\{ww \mid w \text{ belongs to } \{a,b\}*\} $$

where we need to find it it is regular or not. Pumping lemma can be used for irregularity but how to justify in a case where it can be regular?

share|improve this question

4 Answers 4

up vote 1 down vote accepted

Suppose the language was regular and had a DFA.

After reading, for example, "$\underbrace{aa\ldots a}_nb$" the DFA is in some state, and the identity of this state determines completly what the rest of an input that the machine accepts can be.

But if $n\ne m$, then the possible tails that can follow $\underbrace{aa\ldots a}_nb$ and $\underbrace{aa\ldots a}_m b$ are different sets. That means that the machine must be in different states after having read them.

Now, remember what the F in DFA stands for?

share|improve this answer

This language is not regular.

HINT Suppose that it is, then the pumping lemma should hold.

Let $p$ be the pumping length, and pick $w = a^pba^pb$. Can you procede now?

share|improve this answer

An alternative way of proving a language is regular/irregular is the Myhill-Nerode theorem.

share|improve this answer

I don't think it is regular. Try to use the pumping lemma.

share|improve this answer
    
The OP says he doesn't know how to justify the use of the pumping lemma. You say "Try to use the pumping lemma." This is not helpful. –  mixedmath Jun 17 '12 at 1:49
    
My intention was to let the OP know he had the wrong idea. Essentially the only way to prove a language is not regular is to use the pumping lemmma and the only way to show it is regular is to build it up from smaller regular languages. For the language of the problem there is a matching required, the string is split in two equal parts. That is something that can't be done with a regular language unless it is finite. –  i. m. soloveichik Jun 17 '12 at 14:56
    
@i.m.soloveichik: That's patently false. There are excellent ways to prove a language non-regular without using the pumping lemma. In fact, I don't recall ever having seen any application of the pumping lemma that wouldn't have been much simpler and more intuitive with Myhill-Nerode instead. The main advantage of the pumping lemma seems to me to be that it has a memorable name (and very good PR). –  Henning Makholm Jun 17 '12 at 21:53

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.