0
$\begingroup$

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?

$\endgroup$

3 Answers 3

2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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