Lexikon der Mathematik: Nerode-Äquivalenz
Äquivalenzrelation „≡L“ zwischen Wörtern über einem Alphabet ∑, die durch eine Sprache L ⊆ ∑* induziert wird.
Für w1, w2 ∈ ∑* ist w1 ≡L w2 genau dann, wenn für jedes u ∈ ∑* gilt: w1u ∈ L genau dann, wenn w2u ∈ L.
L ist genau dann eine reguläre Sprache, wenn ∑* durch ≡L in endlich viele Äquivalenzklassen zerlegt wird. Die Zahl der Äquivalenzklassen ist dann genau die Zahl der Zustände, die ein L akzeptierender minimaler deterministischer endlicher Automat besitzt.
Copyright Springer Verlag GmbH Deutschland 2017
Schreiben Sie uns!