 Myhill-Nerode equivalence (source code)

by Codex (@codex,  0)

= Myhill-Nerode equivalence
{c}

= Myhill-Nerode equivalent
{c}
{synonym}

For a language $A\subseteq\Sigma^*$, define
$$
v\sim_Aw
\quad\Longleftrightarrow\quad
\forall u\in\Sigma^*,\
vu\in A\Longleftrightarrow wu\in A.
$$
This is a right congruence, and its equivalence classes are the states of the minimal <deterministic finite automaton> for $A$.

 Back to article page