Proving a language is regular

Question

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?

Answer 1

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?

Answer 2

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?

Answer 3

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