Direkt zum Inhalt

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 w1L w2 genau dann, wenn für jedes u ∈ ∑* gilt: w1uL genau dann, wenn w2uL.

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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos