I've been trying to understand the idea behind proving a language is not regular by using Nerode's theorem, but I just couldn't apply the idea on what I've been asked.

The problem is to prove the following languages are non-regular:

  • $L_1 = \{waw^R \mid w∈{a,b}^* \}$, the language of all odd-length palindromes over $\{a,b\}$ such that in the middle of the palindrome there is an $a$.

  • $L_2=\{a^i b^j c^{i+j} \mid i,j∈\mathbb N\}$

  • $L_3=\{a^{2n} b^n \mid n∈\mathbb N\}$

  • $L_4=\{w^2 \mid w∈\{a,b\}^*, \text{$w$ is a palindrome}\}$

Any help will be appreciated.

  • 1
    $\begingroup$ Can you prove any language is not regular using Nerode's theorem? $\endgroup$ – Yuval Filmus May 21 at 15:22
  • $\begingroup$ No, this is my first exercise. But I've been trying to apply the idea of showing that there are infinite equivalence classes by showing that there are infinite objects in different classes, but I have no idea what are the equivalence classes of each language (That is how other people solved other examples online, from what I've seen). $\endgroup$ – Asher Castro May 21 at 16:06
  • $\begingroup$ There’s absolutely no reason to identify equivalence classes. It’s a pity you weren’t presented any examples in class. Complain to the professor. $\endgroup$ – Yuval Filmus May 21 at 16:08
  • $\begingroup$ Well, complains won't help me achieve any knowledge... If what I said is the wrong way, I'll be happy to be presented with the correct way. $\endgroup$ – Asher Castro May 21 at 16:18
  • 1
    $\begingroup$ See this answer for an example of applying Nerode's theorem. $\endgroup$ – Yuval Filmus May 21 at 16:19

Your Answer

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

Browse other questions tagged or ask your own question.