I want to find the equivalence classes (Nerode-relation) of this language:
$L = \{ij\ |\ i,j \in \{a,b\}^*,\ i \neq j\}$
It says that this language is regular and that it has 2 equivalence classes, and I need to prove it. But I just can't find out how to get them. I can't even figure out how that language is regular at all. First I thought it would be as easy as only accepting uneven-length words, but then words like $ababbaba$ wouldn't get accepted. Tried thinking about even/uneven numbers of $b$'s, $a$'s, infixes etc. I tried constructing some automatas, which should be possible with just 2 states, but I just can't get one that works. If I had a regular expression I could find them I'm pretty sure, but I'm having a hard time wrapping my head around this.
Can someone show me how that language would look as a regular expression or as an automata?
I suppose that the alphabet $\Sigma$ is $\{a,b\}$.
It seems that $L = \Sigma^+$, the set of non-empty words.
Take $w\in L$. Then, $w\in \Sigma$. As $w\in L$, there is $i\neq j\in \Sigma^*$ such that $w = ij$. As $i\neq j$, one of them is non-empty, therefore $w$ is non-empty
Now, take $w\in\Sigma^+$. Then, taking $i=\varepsilon$ and $j=w$ (as $w\neq \varepsilon$, you have indeed $i\neq j$), you have $w = ij$. Thus, $w\in L$.
Therefore, $L$ is clearly regular, for example with expression $(a+b)(a+b)^*$.
The equivalence classes become easy to find: there are two classes, a class containing $\varepsilon$ alone, and a class containing every non-empty word.