Informatik

Was ist die Nerode-Relation einer Sprache?

Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* definiert man:

x≡Ly  ⟺  ∀z∈Σ∗:xz∈L⇔yz∈L.x\equiv_L y \iff \forall z\in\Sigma^*: xz\in L \Leftrightarrow yz\in L.

Zwei Präfixe sind äquivalent, wenn keine Fortsetzung sie bezüglich LL unterscheiden kann.

x x xz xz x->xz y y yz yz y->yz z beliebige Fortsetzung z z->xz z->yz same immer gleicher L-Status xz->same yz->same