Izrek Myhill-Nerode
Iz E-študij, proste zakladnice študentskega znanja
Izrek pravi, da so naslednje trditve logično ekvivalentne:
- L je jezik nekega končnega avtomata (regularen jezik)
- L je unija določenega števila ekvivalenčnih razredov neke desno invariantne ekvivalenčne relacije R končnega indeksa
- Desno invariantna ekvivalenčna relacija RL, ima končen indeks, kjer je RL definirano kot
- (z besedo: x in y sta ekvivalantna takrat, ko za vse podaljške z velja, da je xz ∈ L natanko takrat, ko je yz ∈ L)
