# Nerode equivalence

 $s_{1}\mathcal{N}_{X}s_{2}\;\;\iff\;\;\forall t\in S(s_{1}t\in X\;\iff\;s_{2}t% \in X)$ (1)

is an equivalence relation  over $S$, called the Nerode equivalence of $X$.

As an example, if $S=(\mathbb{N},+)$ and $X=\{n\in\mathbb{N}\mid\exists k\in\mathbb{N}\mid n=3k\},$ then $m\mathcal{N}_{X}n$ iff $m\mod 3=n\mod 3$.

The Nerode equivalence is right-invariant, i.e., if $s_{1}\mathcal{N}_{X}s_{2}$ then $s_{1}t\mathcal{N}_{X}s_{2}t$ for any $t$. However, it is usually not a congruence    .

The Nerode equivalence is maximal in the following sense:

• if $\eta$ is a right-invariant equivalence over $S$ and $X$ is union of classes of $\eta$,

• then $s\eta t$ implies $s\mathcal{N}_{X}t$.

In fact, let $r\in S$: since $s\eta t$ and $\eta$ is right-invariant, $sr\eta tr$. However, $X$ is union of classes of $\eta$, therefore $sr$ and $tr$ are either both in $X$ or both outside $X$. This is true for all $r\in S$, thus $s\mathcal{N}_{X}t$.

The Nerode equivalence is linked to the syntactic congruence by the following fact, whose proof is straightforward:

 $s_{1}\equiv_{X}s_{2}\;\;\mathrm{iff}\;\;ls_{1}\mathcal{N}_{X}ls_{2}\;\forall l% \in S\;.$
Title Nerode equivalence NerodeEquivalence 2013-03-22 18:52:11 2013-03-22 18:52:11 Ziosilvio (18733) Ziosilvio (18733) 4 Ziosilvio (18733) Definition msc 68Q70 msc 20M35 maximality property of Nerode equivalence