Äquivalenzrelation „≡_L“ zwischen Wörtern über einem Alphabet ∑, die durch eine Sprache L ⊆ ∑* induziert wird.

Für w₁, w₂ ∈ ∑* ist w₁ ≡_Lw₂ genau dann, wenn für jedes u ∈ ∑* gilt: w₁u ∈ L genau dann, wenn w₂u ∈ 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.