The Myhill-Nerode relation $\equiv_L$ of $L$ is a relation on $\Sigma^*$ (not on $L$, so representatives do not have to be members of $L$, as you observed). It is for words $x,y \in \Sigma^*$ defined by
$$
x \equiv_L y \iff \forall z \in \Sigma^*: xz \in L \Leftrightarrow yz \in L
$$
That is, two words are equivalent, iff however we add some $z$ to both of them, we either have to words in $L$ or two words off $L$.
One usually looks at $\equiv_L$ to see a language is or is not regular. To see a language is not regular, one has to give infinitely many words $x_i \in \Sigma^*$ with
$$ x_i \not\equiv_L x_j, \qquad i \ne j $$
That is, why you were given those $z$s, they will be usefull to see your classes listed are indeed different. For example:
$\epsilon \not\equiv_L a$, as with $z = b$ (look at your $K_A$ list), we have $\epsilon z = b \not\in L$, but $az = ab \in L$.
Note moreover that one infinite list suffices, that is if you can show $a^i\not\equiv_L a^j$ for $i \ne j$, you are done in showing that $L$ isn't regular. If you want to find all equivalence classes, there is at least one missing.
In general:
For a general approach I don't know anything better than constructing an automaton, minimizing it, and then recalculating the equivalence classes again. However, there are a few tricks that very often speed up this process, or sometimes even make it unnecessary. Still, this works only because the automatons you usually have to deal with are quite simple, if you were to do this for an automaton with a looooot of states, writing a computer program from scratch that does this would be faster.
Relevant intuition on regular languages:
The regular languages are, intuitively, languages which require only finite amount of information at any given time to decide whether the input belongs or not to the language.
To be more precise, finite amount of information means that there are finitely many variables, each having finitely many possible values.
That means, if we take all the possible configurations, we still end up with finitely many states, and exactly that notion is exemplified by the finite automatons: each state corresponds to some configuration.
That is also why the language of parentheses given by grammar: $X \to X\mathtt{(}X\mathtt{)} \mid \varepsilon$ is not regular – to parse it you need to know at any given moment how many parentheses are open, and that number can be arbitrarily big, so even if that is only one number, it is far more than finite amount of information.
However, this intuition is even more apparent when you consider the syntactic monoid of a language. A different characterization of regular languages is that they are recognizable by finite monoids. In particular, if $M$ is the smallest monoid that recognizes language $L$ via some homomorphism $\phi : \Sigma^* \to M$, then that homomorphism $\phi$ is actually the information filter that distills all the necessary info, and leaves nothing more. Another way to think about it is to imagine that each word $w \in \Sigma^*$ contains some information, but not all that information is needed to decide whether $w \in L$. When we map $w$ into $M$ as $\phi(w)$, then what we get is a finite representation of all the information that can be necessary to deal with $w$ in context of $L$.
The basic trick:
The trick I've mentioned at the beginning is to guess with what info it is possible to decide whether $w \in L$. For example in your case
$$L=\Big\{w \in \{\mathtt{a},\mathtt{b}\}^* \ \Big|\ w=\mathtt{a}v \text{ for a word } v \in\{\mathtt{a},\mathtt{b}\}^* \text{ and } |w|_{\mathtt{b}} \text{ is even}\Big\}$$
with have two bits of information:
- if $w$ starts with $\mathtt{a}$,
- if $|w|_{\mathtt{b}}$ is even.
This implies that we will need at most $2\cdot2 = 4$ states, and this is what you get. Such guessing requires a bit of insight, for example
$$L_3=\Big\{w \in \{\mathtt{a},\mathtt{b}\}^* \ \Big|\ w=\mathtt{a}v \text{ for a word } v \in\{\mathtt{a},\mathtt{b}\}^* \text{ and } |w|_{\mathtt{b}} \text{ is divisible by } 3\Big\}$$
also seems to have 2 bits of information, but actually we need 6 states.
The new condition $|w|_{\mathtt{b}} \text{ is divisible by } 3$ requires three states to handle (remainder $0$, $1$ and $2$), so that when we concatenate two words $w_1$ and $w_2$ we will be able to tell the new value just from values of $w_1$ and $w_2$ instead of looking at the whole words (with only two possible values we wouldn't be able to tell the difference between $|w_1|_{\mathtt{b}} = 1 = |w_2|_{\mathtt{b}}$ and $|w_1|_{\mathtt{b}} = 1, |w_2|_{\mathtt{b}} = 2$).
Some caveats:
Now that we are able to identify all the atoms (compare with atoms in probability), we can generate some equivalence classes, but these may not be minimal. For example consider
$$L_\vee=\Big\{w \in \{\mathtt{a},\mathtt{b}\}^* \ \Big|\ w=\mathtt{a}v \text{ for a word } v \in\{\mathtt{a},\mathtt{b}\}^* \text{ or } |w|_{\mathtt{b}} \text{ is divisible by } 3\Big\}$$
Of course, we can split $\Sigma^*$ into six equivalence classes that suffice to handle $L$:
$$\{\text{starts_with_}\mathtt{a},\text{starts_with_}\mathtt{b}\}
\times\{\text{rem_}0,\text{rem_}1,\text{rem_}2\},$$
but we need only $4$, the remainders of $|w|_{\mathtt{b}} \bmod 3$ are necessary only if $w$ does not start with $\mathtt{a}$:
$$\{
\text{sw}\mathtt{a},
\text{sw}\mathtt{b}\text{_rem_}0,
\text{sw}\mathtt{b}\text{_rem_}1,
\text{sw}\mathtt{b}\text{_rem_}2
\}.$$
Closing word:
There is a lot of things to consider and this is not a place for me to dwell on them, however, if you start thinking this way, a lot of structure will "pop out". One nice example to practice on is
$$L_{10} = \Big\{ w \in \{\mathtt{a},\mathtt{b}\} \ \Big|\
\text{the 10-th letter of $w$ from the back is }\mathtt{a}\Big\}.$$
It is easy to construct NFA for $L_{10}$, but DFA will have a lot of states. Yet, if you think about it it makes a lot of sense, because the info the syntactic monoid will want you to remember contains at least $10$ bits, i.e. whether the $i$-th letter from the back is $\mathbb{a}$ or not. In other words, you need a way to represent a 10-bit number, so you have to have at least $2^{10}$ different equivalence classes or states in any deterministic finite automaton that recognizes $L_{10}$.
So that was one basic trick and some hints on how to extend it. It's not magic, but it simplified things for me a lot, perhaps you will like this approach too.
I hope this helps $\ddot\smile$
Best Answer
Your first idea is correct.
Let $\sim$ be the Myhill-Nerode equivalence relation for the language $\{0,1\}^*$ over the alphabet $\Sigma=\{0,1\}$. Then for $x,y\in\Sigma^*$ we have $x\sim y$ if and only if for each $z\in\Sigma^*$ either $xz\in L$ and $yz\in L$, or $xz\notin L$ and $yz\notin L$. Since $L=\Sigma^*$, it’s clear that for any $x,y,z\in\Sigma^*$ we have $xz\in L$ and $yz\in L$, so $x\sim y$ for all $x,y\in\Sigma^*$, and there is indeed only one $\sim$-equivalence class: $[x]=\Sigma^*$ for each $x\in\Sigma^*$. In particular, $[x]=[\epsilon]$ for all $x\in\Sigma^*$.