Satz von Myhill und Nerode

Definition: Äquivalenzrelation für Sprache

Es gilt genau dann, wenn für alle Wörter gilt:

Äquivalenzklasse:

Anzahl erzeugter Äquivalenzklassen: Index von

Eine Sprache ist genau dann regulär, wenn der Index von endlich ist.

Satz: Satz von Rice Chomsky-Hierachie