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 lleva el nombre de John Myhill y Anil Nerode , quienes lo demostraron en la Universidad de Chicago en 1958 ( Nerode 1958 ).

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

El teorema de Myhill-Nerode establece que una lengua es regular si y solo si 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 reconocimiento de autómatas finitos deterministas mínimos (DFA) . En particular, esto implica que existe un DFA mínimo único para cada idioma regular ( Hopcroft y Ullman 1979 ).${\ Displaystyle L}$${\ Displaystyle {} _ {L} {\ sim}}$ ${\ Displaystyle L}$

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

---