0
$\begingroup$

Prove using the Myhill-Nerode theorem that the language $L = \{xyz| x,y \in\{a,b\}^+\}$ - is not regular

My answer:

To prove that $L$ is not regular, we need to show that there are infinitely many distinct equivalence classes for $L$.

Consider the strings of the form $๐‘Ž^i$ and $๐‘Ž^๐‘–๐‘$ for $๐‘– โ‰ฅ1$:

Let $x_i = a^i$ and $y = b$.

For any $i,j \ge 1$, consider $x_i = a^i$ and $x_j = a^j$.

Show that $x_i$ and $x_j$ are in Different Equivalence Classes:

For $x_i = a^i$, $x_i y x_i=a^i b a^i \in L$.

For $x_j= a^j, x_j y x_j = a^j b a^j \in L$.

If $i \ne j $, then $a^i b a^i \ne a^j b a^j$

because the number of $a$'s before and after the $b$ would be different.

Thus, $a^i$ and $a^j$ belong to different equivalence classes for $i\ne j $.

Since there are infinitely many choices for $i$, there are infinitely many distinct equivalence classes.

Thus this explanation ok to show the language is not regular?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

As I understand it, your goal is to prove that the language of palindromes is not regular, using the Myhill-Nerode theorem.

You have a good start to the proof. You'll want to be a little careful about showing equivalence. The step $a^iba^i \neq a^jba^j$ is not quite the right thing to show. What you need to show is that the extension $z\equiv \mathtt{ba}^i$ makes $x=\mathtt{a}^i$ into a palindrome but doesn't make $y=\mathtt{a}^j$ $(i\neq j)$ into a palindrome. When an extension $z$ makes $xz$ belong to the language and $yz$ not belong to the language, the strings $x$ and $y$ are in different equivalence classes.

Your proof idea is solid though, with this modification. Using a string with A on the left and right and B in the middle is a good candidate.

Theorem: The language of palindromes $\{xx^R : x\in\{\mathtt{a},\mathtt b\}^*\}$ is not regular.

Proof: Pick any string length $n>0$ and consider the set of all strings $\{\mathtt{a},\mathtt{aa}, \mathtt{aaa}, \ldots, \mathtt{a}^n\}$. There are $n$ different strings. Furthermore, we can prove that they all belong to different equivalence classes: if $x=a^i$ and $y=a^j$, define $z\equiv ba^{i}$. If $i\neq j$, then $xz=a^iba^i$ is a palindrome but $yz=a^jba^{i}$ isn't. This means that $x$ and $y$ must belong to different equivalence classes. Because this reasoning works for any pair of strings of this form, those $n$ strings must all belong to distinct equivalence classes. But our choice of $n$ was arbitrary; hence the language contains an infinite number of equivalence classes and is therefore not regular. $\square$

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.