Die Nerode-Rechtskongruenz

Definition

Es sei $L\subseteq {\Sigma }^{\ast }$ eine Sprache. Für $u,v\in \Sigma$ definiren wir:
$u{\simeq }_{L}v⟺\forall w\in {\Sigma }^{\ast }:uw\in L⟺vw\in L$

Satz von Myhill und Nerode

Definition

Eine Sprache $L$ ist regulär genau dann, wenn Die Nerode-Rechtskongruenz ${\simeq }_L$ einen endlich Index hat.

Link to original

Beispiel

Beweise für Eigenschaften der Nerode-Rechtskongruenz