Teorema de Myhill-Nerode

En la teoría de los lenguajes formales , el teorema de Myhill-Nerode proporciona una condición necesaria y suficiente para que un lenguaje sea regular . El teorema recibe su nombre de John Myhill y Anil Nerode , quienes lo demostraron en la Universidad de Chicago en 1957. ^{[ 1 ]} .

Dado un idioma${\displaystyle L}$y un par de cuerdas${\displaystyle x}$y${\displaystyle y}$, definir una extensión distintiva como una cadena${\displaystyle z}$de tal manera que exactamente una de las dos cuerdas${\displaystyle xz}$y${\displaystyle yz}$pertenece a${\displaystyle L}$. Definir una relación${\displaystyle \sim _{L}}$en cuerdas como${\displaystyle x\;\sim _ {L}\ y}$si no hay una extensión distintiva para${\displaystyle x}$y${\displaystyle y}$Es fácil demostrar que${\displaystyle \sim _{L}}$es una relación de equivalencia en cadenas, y por lo tanto divide el conjunto de todas las cadenas en clases de equivalencia .

El teorema de Myhill-Nerode establece que un lenguaje${\displaystyle L}$es regular si y solo si${\displaystyle \sim _{L}}$tiene un número finito de clases de equivalencia y, además, que este número es igual al número de estados en el autómata finito determinista mínimo (AFD) que acepta${\displaystyle L}$. Además, cada DFA mínimo para el lenguaje es isomorfo al canónico. ^{[ 2 ]} .

En general, para cualquier lenguaje, el autómata construido es un autómata de estados que acepta estados. Sin embargo, no necesariamente tiene un número finito de estados. El teorema de Myhill-Nerode demuestra que la finitud es necesaria y suficiente para la regularidad del lenguaje.

Algunos autores se refieren a la${\displaystyle \sim _{L}}$relación como congruencia de Nerode , ^{[ 3 ] [ 4 ]} en honor a Anil Nerode .

El teorema de Myhill-Nerode puede utilizarse para demostrar que un lenguaje${\displaystyle L}$es regular al demostrar que el número de clases de equivalencia de${\displaystyle \sim _{L}}$es finito. Esto se puede hacer mediante un análisis exhaustivo de casos en el que, partiendo de la cadena vacía , se utilizan extensiones distintivas para encontrar clases de equivalencia adicionales hasta que no se puedan encontrar más.

Por ejemplo, el lenguaje que consiste en representaciones binarias de números que se pueden dividir por 3 es regular. Dadas dos cadenas binarias${\displaystyle x,y}$, extendiéndolos por un dígito se obtiene${\displaystyle 2x+b,2y+b}$, entonces${\displaystyle 2x+b\equiv 2y+b\mod 3}$si y solo si${\displaystyle x\equiv y\mod 3}$. De este modo,${\displaystyle 00}$(o${\displaystyle 11}$),${\displaystyle 01}$, y${\displaystyle 10}$son las únicas extensiones distintivas, lo que da como resultado las 3 clases. El autómata mínimo que acepta nuestro lenguaje tendría tres estados correspondientes a estas tres clases de equivalencia.

Otro corolario inmediato del teorema es que si para un lenguaje${\displaystyle L}$la relación${\displaystyle \sim _{L}}$Si un lenguaje tiene infinitas clases de equivalencia, no es regular. Este corolario se utiliza con frecuencia para demostrar que un lenguaje no es regular.

El teorema de Myhill-Nerode puede generalizarse a autómatas de árbol . ^{[ 5 ]}

• El lema de bombeo para lenguajes regulares es un método alternativo para demostrar que un lenguaje no es regular. Sin embargo, este lema no siempre permite demostrar la regularidad de un lenguaje.
• Monoide sintáctico