1

I have to use the Myhill-Nerode theorem for the following language:

$$L = \left\{ a^n b^n\mid n\ \geq\ 1 \right\}$$

An equivalence relation is the following: $$x \sim y\ \Leftrightarrow \forall\ \ z\ \in \Sigma ^*\ : xz\ \in\ L\ \Leftrightarrow\ yz\ \in\ L$$

I thought that since $a^ib^j$ and $a^jb^j$ for $i \neq j$ belong to two different equivalence classes, and $i,j \in \mathbb{N}$, there are infinite many equivalence classes, so the language $L$ is not regular.

Is this correct?

And is the way I formulated the answer correct? Or is there a better way to construct the answer?

Michael Hardy
  • 1
Mary Star
  • 13,956

1 Answers1

1

I'm not quite clear about your answer, I think probably if you gave a bit more explanation it would be fine. Perhaps a simpler way would be to consider the words $a^nb$ for $n\ge1$. We have $$a^nbz\in L\quad\Leftrightarrow\quad z=b^{n-1}\ ,$$ and so $a^mb$ is never equivalent to $a^nb$ if $m\ne n$. So there are infinitely many equivalence classes.

IMO it is even easier if you have done the formulation of the MNT using tails. We have $$T(a^nb)=\{z\in\Sigma^*\mid a^nbz\in L\}=\{b^{n-1}\}$$ and so there are infinitely many different tails.

David
  • 82,662