Indietro

ⓘ Teorema di Myhill-Nerode




                                     

ⓘ 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 sullalfabeto Σ {\displaystyle \Sigma } consiste nellunione di classe di equivalenza di una relazione invariante a destra di indice finito sulla chiusura di Kleene di Σ {\displaystyle \Sigma }.

                                     

1. Definizioni

Dato un automa a stati finiti deterministico M = {\displaystyle M=\leftQ,\Sigma,\delta,q_{0},F\right} si definisce la relazione di equivalenza

R M: x R M y ⟺ δ ^ q 0, x = δ ^ q 0, y {\displaystyle R_{M}:xR_{M}y\Longleftrightarrow {\hat {\delta }}\leftq_{0},x\right={\hat {\delta }}\leftq_{0},y\right}

Tale relazione di equivalenza è invariante a destra se:

δ ^ q 0, x z = δ ^ δ ^ q 0, x, z) = δ ^ δ ^ q 0, y, z) = δ ^ q 0, y z {\displaystyle {\hat {\delta }}\leftq_{0},xz\right={\hat {\delta }}\left{\hat {\delta }}\leftq_{0},x\right,z\right)={\hat {\delta }}\left{\hat {\delta }}\leftq_{0},y\right,z\right)={\hat {\delta }}\leftq_{0},yz\right} supponendo x R M y {\displaystyle xR_{M}y}.
                                     

2. Enunciato del teorema

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

  • L ⊆ Σ ∗ {\displaystyle L\subseteq \Sigma ^{*}} è regolare
  • la relazione di equivalenza: ∀ x, y ∈ Σ ∗, x R L y ⟺ ∀ z ∈ Σ ∗, x z ∈ L ⟺ y z ∈ L {\displaystyle \forall x,y\in \Sigma ^{*},xR_{L}y\Longleftrightarrow \forall z\in \Sigma ^{*},xz\in L\Longleftrightarrow yz\in L} è di indice finito.
  • L {\displaystyle L} è lunione 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. Usi e conseguenze

La diretta conseguenza del teorema di Myhill-Nerode è che un linguaggio L {\displaystyle L} è regolare se e solo se il numero di classi di equivalenza della relazione R L {\displaystyle 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.