As an example, if and then iff .
The Nerode equivalence is right-invariant, i.e., if then for any . However, it is usually not a congruence.
The Nerode equivalence is maximal in the following sense:
if is a right-invariant equivalence over and is union of classes of ,
then implies .
In fact, let : since and is right-invariant, . However, is union of classes of , therefore and are either both in or both outside . This is true for all , thus .
The Nerode equivalence is linked to the syntactic congruence by the following fact, whose proof is straightforward:
|Date of creation||2013-03-22 18:52:11|
|Last modified on||2013-03-22 18:52:11|
|Last modified by||Ziosilvio (18733)|
|Defines||maximality property of Nerode equivalence|