Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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?
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?
An alternative way of proving a language is regular/irregular is the Myhill-Nerode theorem.
