Nella teoria dei linguaggi formali il teorema di Myhill-Nerode fornisce una condizione necessaria e sufficiente per stabilire se un linguaggio sia regolare o meno.
Secondo il teorema di Myhill-Nerode, ogni linguaggio regolare sull'alfabeto consiste nell'unione di classe di equivalenza di una relazione invariante a destra di indice finito sulla chiusura di Kleene di .
Definizioni Dato un automa a stati finiti deterministico si definisce la relazione di equivalenza
Tale relazione di equivalenza è invariante a destra se: supponendo .
Enunciato del teorema Il teorema di Myhill-Nerode afferma che sono equivalenti le affermazioni: è regolare è l'unione di alcune classi di equivalenza di una relazione di equivalenza di indice finito (ossia che individua un numero finito di classi di equivalenza) invariante a destra la relazione di equivalenza: è di indice finito.
Usi e conseguenze La diretta conseguenza del teorema di Myhill-Nerode è che un linguaggio è regolare se e solo se il numero di classi di equivalenza della relazione è finito. Come corollario, un linguaggio che definisca un insieme infinito di classi di equivalenza non è regolare. Tale corollario può essere usato per dimostrare la non regolarità di un linguaggio.
Bibliografia
Voci correlate Pumping lemma per i linguaggi regolari
Categoria:Teoria dei linguaggi formali