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 (Nerode y Sauer, 1957, p. ii).

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 (Hopcroft y Ullman, 1979).

(1) $L$ es regular si y solo si $\sim _{L}$ tiene un número finito de clases de equivalencia. (2) Este número es igual al número de estados en el autómata finito determinista mínimo (AFD) que acepta $L$. (3) Cualquier aceptador del AFD mínimo para el lenguaje es isomorfo al siguiente: Sea cada clase de equivalencia $[x]$ correspondiente a un estado, y sean las transiciones de estado $a:[x]\to [xa]$ para cada $a\in \Sigma$. Sea el estado inicial $[\epsilon ]$, y los estados de aceptación sean $[x]$ donde $x\in L$. Myhill, Nerode (1957)

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.

Demostración

(1) Si $L$ es regular, construir un DFA mínimo para aceptarlo. Claramente, si $x,y$ terminan en el mismo estado después de ejecutarse a través del DFA, entonces $x\sim _{L}y$, por lo tanto, el número de clases de equivalencia de $\sim _{L}$ es como máximo el número de estados del DFA, que debe ser finito. Por el contrario, si $\sim _{L}$ tiene un número finito de clases de equivalencia, entonces el autómata de estados construido en el teorema es un aceptor de AFD, por lo tanto, el lenguaje es regular. (2) Por la construcción en (1). (3) Dado un aceptor DFA mínimo $A$, construimos un isomorfismo al canónico. Construya la siguiente relación de equivalencia: $x\sim _{A}y$ si y solo si $x,y$ terminan en el mismo estado al pasar por $A$. Como $A$ es un aceptor, si $x\sim _{A}y$ entonces $x\sim _{L}y$. Por lo tanto, cada clase de equivalencia $\sim _{L}$ es una unión de una o más clases de equivalencia de $\sim _{A}$. Además, como $A$ es mínima, el número de estados de $A$ es igual al número de clases de equivalencia de $\sim _{L}$ por la parte (2). Por lo tanto, $\sim _{A}=\sim _{L}$. Ahora bien, esto nos da una biyección entre los estados de $A$ y los estados del aceptor canónico. Es claro que esta biyección también preserva las reglas de transición, por lo que es un isomorfismo de AFD.

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, not 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

• Hopcroft, John E.; Ullman, Jeffrey D. (1979), «Chapter 3.4», Introduction to Automata Theory, Languages, and Computation, Reading, Massachusetts: Addison-Wesley Publishing, ISBN 0-201-02988-X ..
• Nerode, Anil (1958), «Linear Automaton Transformations», Proceedings of the American Mathematical Society 9 (4): 541-544, doi:10.1090/S0002-9939-1958-0135681-9 ..
• Nerode, Anil; Sauer, Burton P. (Nov 1957), Fundamental Concepts in the Theory of Systems (57–624), Wright Air Development Center .. ASTIA Document No. AD 155741.
• Regan, Kenneth (2007), Notes on the Myhill-Nerode Theorem, consultado el 22 de marzo de 2016 ..

Lectura adicional

• Bakhadyr Khoussainov; Anil Nerode (6 December 2012). Automata Theory and its Applications. Springer Science & Business Media. ISBN 978-1-4612-0171-7. 

• Datos: Q422187