1
$\begingroup$

I know pumping lemma and also know how to prove if languages are not regular or are regular using proof by contradiction methodology. But I am stuck on this one.Especially, I don't know exact string it produces.

$$ H = \{www \mid w ∊ (0,1)^* \} $$

How do I prove this is not regular language? Thanks!

$\endgroup$
1
1
$\begingroup$

You can use the Myhill–Nerode criterion. Consider the words $0^n1$ for all $n$. These are pairwise inequivalent since $0^n10^n10^n1 \in H$ while $0^m10^n10^n1 \notin H$ if $m \neq n$. Since we have found infinitely many pairwise inequivalent words, it follows that the language is not regular.

As mentioned in the comments, you can probably also use the pumping lemma, but it might take more work.

$\endgroup$
1
  • $\begingroup$ Sorry, I completely forgot to accept your answer. Thanks for the answer $\endgroup$
    – Chu
    Mar 24 '18 at 2:22

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.