title: Teorema di Myhill-Nerode
text: # 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 $\Sigma$ consiste nell'unione di classe di equivalenza di una relazione invariante a destra di indice finito sulla chiusura di Kleene di $\Sigma$.
  
  ## Definizioni
  
  Dato un automa a stati finiti deterministico $M=\left(Q,\Sigma ,\delta ,q_{0},F\right)$ si definisce la relazione di equivalenza
  
      $R_{M}:xR_{M}y\Longleftrightarrow {\hat {\delta }}\left(q_{0},x\right)={\hat {\delta }}\left(q_{0},y\right)$
  
  Tale relazione di equivalenza è invariante a destra se:
  
      ${\hat {\delta }}\left(q_{0},xz\right)={\hat {\delta }}\left({\hat {\delta }}\left(q_{0},x\right),z\right)={\hat {\delta }}\left({\hat {\delta }}\left(q_{0},y\right),z\right)={\hat {\delta }}\left(q_{0},yz\right)$ supponendo $xR_{M}y$.
  
  ## Enunciato del teorema
  
  Il teorema di Myhill-Nerode afferma che sono equivalenti le affermazioni:
  
  * $L\subseteq \Sigma ^{*}$ è regolare
  * $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
  * la relazione di equivalenza: $\forall x,y\in \Sigma ^{*},xR_{L}y\Longleftrightarrow \forall z\in \Sigma ^{*},xz\in L\Longleftrightarrow 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.
  
  