1
$\begingroup$

Let $L = \{\alpha\in\{a,b,c\}^{*} \mid \alpha \text{ is palindrome}\}$, show that $L$ is not regular using Myhill-Nerode relation.

I don't know how to show that $L$ has infinite equivalence classes because $\alpha$ is a palindrome. I tried to use something like this, but I don't know if its correct:

$\alpha \equiv_{L} \beta \iff \alpha (aba)^k \in{L} \iff \beta (aba)^k \in{L}$ $\forall k \in \mathbb N$ which implies that for every k there exists an equivalence class because the repetition of aba k times.

$\endgroup$
1
$\begingroup$

Take $a^nb$ and $a^mb$ for n != m. Since the first can be followed by $a^n$ and the second can’t, they are in different equivalence classes. Therefore the number of equivalence classes is not finite.

C isn’t even needed.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

You seem to have forgotten the letter $c$ inside your parenthesis. According to this university handout, an equivalence class requires that appending every string in the alphabet to the two equivalent inputs still makes these two inputs either both in the language or both not in the language. In other words,

$\alpha \equiv_L \beta$ means $\alpha y \in L \wedge \beta y \in L$ for any $y$ in your three letter alphabet, or $\alpha y \not\in L \wedge \beta y \not\in L$.

$y = (aba)^k$ is not all possible string in the alphabet.

One strategy in the handout is to start with one equivalence class and append the same string to two members of the equivalence class. Then show that the resulting two strings are no longer equivalent, ie. one is in the language while the other one is not. It is a proof by contradiction by first assuming the language is regular.

| cite | improve this answer | |
$\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.