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

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

${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle xR_{M}y}$.

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

1. ${\displaystyle L\subseteq \Sigma ^{*}}$ è regolare
2. ${\displaystyle 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: ${\displaystyle \forall x,y\in \Sigma ^{*},xR_{L}y\Longleftrightarrow \forall z\in \Sigma ^{*},xz\in L\Longleftrightarrow yz\in L}$ è di indice finito.

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

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

• Pumping lemma per i linguaggi regolari

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