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

3 Answers 3

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

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.