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:

1. $L\subseteq\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: $\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.

Bibliografia

• Nerode, Anil (agosto 1958). Linear Automaton Transformations. Proceedings of the American Mathematical Society 9 (4): pp. 541-544  (in inglese). URL consultato in data 11 giugno 2011.
• Jan van Leeuwen, Lower bounds: formal language theory in Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity (in inglese), The MIT Press, 4 gennaio 1994. ISBN 978-0262720144
• Martin Davis; Ron Sigal; Elaine J. Weyuker, The Myhill-Nerode Theorem in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (in inglese), Morgan Kaufmann, 17 febbraio 1994. ISBN 978-0122063824

Voci correlate

• Pumping lemma per i linguaggi regolari

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica