Teorema di Myhill-Nerode

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 $\mathrm{\Sigma }$ consiste nell'unione di classe di equivalenza di una relazione invariante a destra di indice finito sulla chiusura di Kleene di $\mathrm{\Sigma }$.

Definizioni

Dato un automa a stati finiti deterministico $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ si definisce la relazione di equivalenza

$R_M:x{R}_{M}y⟺\hat{\delta }(q_0,x)=\hat{\delta }(q_0,y)$

Tale relazione di equivalenza è invariante a destra se:

$\hat{\delta }(q_0,xz)=\hat{\delta }(\hat{\delta }(q_0,x),z)=\hat{\delta }(\hat{\delta }(q_0,y),z)=\hat{\delta }(q_0,yz)$ supponendo $x{R}_{M}y$.

Enunciato del teorema

Il teorema di Myhill-Nerode afferma che sono equivalenti le affermazioni:

1. $L\subseteq {\mathrm{\Sigma }}^{*}$ è regolare
2. $L$ è 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
3. la relazione di equivalenza: $\mathrm{\forall }x,y\in {\mathrm{\Sigma }}^{*},x{R}_{L}y⟺\mathrm{\forall }z\in {\mathrm{\Sigma }}^{*},xz\in L⟺yz\in L$ è di indice finito.

Usi e conseguenze

La diretta conseguenza del teorema di Myhill-Nerode è che un linguaggio $L$ è regolare se e solo se il numero di classi di equivalenza della relazione $R_L$ è 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

• Template:Cita pubblicazione
• Template:Cita libro
• Template:Cita libro

Voci correlate

• Pumping lemma per i linguaggi regolari