Teorema de Myhill-Nerode

En la teoria de llenguages formals, la teorema de Myhill-Nerode proporciona una condició necessària i suficient per a que un llenguage siga regular. La teorema deu el seu nom a John Myhill i Anil Nerode, els qui ho varen demostrar en l'Universitat de Chicago en 1957 (Nerode y Sauer, 1957, p. ii).

Enunciat

Donat un llenguage $L$, i un parell de cadenes $x$ i $y$, definix una extensió distintiva per a que siga una cadena $z$ de manera que exactament una de les dos cadenes $xz$ i $yz$ pertany a $L$ . Definir una relació ${\sim }_L$ en cuerdo com $x{\sim }_{L}y$ si no hi ha una extensió distintiva per a $x$ i $y$ . És fàcil demostrar que ${\sim }_L$ és una relació d'equivalència en cadenes i, per lo tant, dividix el conjunt de totes les cadenes en classes d'equivalència.

La teorema de Myhill-Nerode establix que un llenguage $L$ és regular si i només si ${\sim }_L$ té un número finito de classes d'equivalència i, ademés, que este número és igual al número d'estats en l'autómata finito determinista mínim (AFD) que accepta $L$ . Ademés, cada AFD mínim per al llenguage és isomorfo al canònic (Hopcroft y Ullman, 1979).

Generalment, per a qualsevol llenguage, l'autómata construït és un acceptor d'autómates d'estats. No obstant, no necessàriament té un número finito d'estats. La teorema de Myhill-Nerode mostra que la finitud és necessària i suficient per a la regularitat del llenguage.

Alguns autors fan referència a la ${\sim }_L$ relació com a congruència de Nerode, en honor a Anil Nerode.

Us i conseqüències

La teorema de Myhill-Nerode es pot utilisar per a demostrar que un llenguage $L$ és regular demostrant que el número de classes d'equivalència de ${\sim }_L$ és finito. Açò es pot fer per mig d'un anàlisis de cas exhaustiu en el que, a partir de la cadena buida, s'utilisen extensions distintives per a trobar classes d'equivalència adicionals fins que no es puguen trobar més. Per eixemple, el llenguage que consistix en representacions binarias de números que poden dividir-se per 3 és regular. Donada la cadena buida, $00$ (o $11$ ), $01$, i $10$ són extensions distintives que donen com resultat les tres classes (corresponents a números que donen com a residu 0, 1 i 2 quan es dividixen per 3), pero despuix d'este pas ya no hi ha més extensió distintiva. L'autómata mínim que accepte el nostre llenguage tindria tres estats corresponents a estes tres classes d'equivalència.

Un atre corolari immediat de la teorema és que si per a un llenguage $L$ La relació ${\sim }_L$ té infinites classes d'equivalència, és regular. Est és el corolari que s'utilisa en freqüència per a demostrar que una llengua no és regular.

Vore també

• Lema de bombeig per a llenguages regulars, un método alternatiu per a demostrar que un llenguage no és regular. El lema de bombeig no sempre pot demostrar que un llenguage no és regular.
• Monoide sintàctic

Bibliografia

• .
• .
• . ASTIA Document No. AD 155741.
• .