Teorema de Myhill-Nerode

En la teoría de lenguajes formales, el teorema de Myhill-Nerode proporciona una condición necesaria y suficiente para que un lenguaje sea regular. El teorema debe su nombre a John Myhill y Anil Nerode, quienes lo demostraron en la Universidad de Chicago en 1957 Plantilla:Cita Harvard.

Enunciado

Dado un lenguaje $L$, y un par de cadenas $x$ y $y$, define una extensión distintiva para que sea una cadena $z$ de manera que exactamente una de las dos cadenas $xz$ y $yz$ pertenece a $L$ . Definir una relación ${\sim }_L$ en cuerdas como $x{\sim }_{L}y$ si no hay una extensión distintiva para $x$ y $y$ . Es fácil demostrar que ${\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 $L$ es regular si y sólo si ${\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 $L$ . Además, cada AFD mínimo para el lenguaje es isomorfo al canónico Plantilla:Cita Harvard.

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

Algunos autores hacen referencia a la ${\sim }_L$ relación como congruencia de Nerode, en honor a Anil Nerode.

Uso y consecuencias

El teorema de Myhill-Nerode se puede utilizar para demostrar que un lenguaje $L$ es regular demostrando que el número de clases de equivalencia de ${\sim }_L$ es finito. Esto se puede hacer mediante un análisis de caso exhaustivo en el que, a partir 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 pueden dividirse por 3 es regular. Dada la cadena vacía, $00$ (o $11$ ), $01$, y $10$ son extensiones distintivas que dan como resultado las tres clases (correspondientes a números que dan como residuo 0, 1 y 2 cuando se dividen por 3), pero después de este paso ya no hay más extensión distintiva. El autómata mínimo que acepte nuestro lenguaje tendría tres estados correspondientes a estas tres clases de equivalencia.

Otro corolario inmediato del teorema es que si para un lenguaje $L$ La relación ${\sim }_L$ tiene infinitas clases de equivalencia, Plantilla:Enf es regular. Este es el corolario que se utiliza con frecuencia para demostrar que una lengua no es regular.

Generalizaciones

El teorema de Myhill-Nerode se puede generalizar a los autómatas de árbol.

Véase también

• Lema de bombeo para lenguajes regulares, un método alternativo para demostrar que un lenguaje no es regular. El lema de bombeo no siempre puede demostrar que un lenguaje no es regular.
• Monoide sintáctico

Bibliografía

• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada. ASTIA Document No. AD 155741.
• Plantilla:Obra citada.

Lectura adicional

• Plantilla:Cita libro