El teorema de Myhill Nerode es un resultado fundamental de la teoría de los lenguajes. Esta teoría fue probada por John Myhill y Anil Nerode en 1958. Se usa para probar si un lenguaje L es regular o no y también se usa para minimizar estados en DFA (Deterministic Finite Automata).
Para comprender este teorema, primero debemos comprender qué es la indistinguibilidad :
Dado un lenguaje L y x,y son strings sobre ∑*, si para cada string z ∈ ∑*, xz, yz ∈ L o xz, yz ∉ L entonces se dice que x e y son indistinguibles sobre el lenguaje L. Formalmente, denote que x e y son indistinguibles sobre L por la siguiente notación: x ≡ L y.
≡ L es una relación de equivalencia ya que es:
1) Reflexiva : Para toda string x, xz ∈ L si y si xz ∈ L por lo tanto x ≡ L x.
2) Simétrico : Supongamos que x ≡ L y. Esto significa xz, yz ∈ L o xz, yz ∉ L para todo z ∈ ∑*. Equivalentemente esto significa yz,xz ∈ L o yz, xz ∉ L para todo z ∈ ∑* lo que implica y ≡ L x
3) Transitiva : supongamos que x ≡ L y y y ≡ L w. Entonces suponga por el bien de la contradicción que x y w no son indistinguibles. Esto significa que debe existir algún z tal que exactamente uno de xz y wz sea miembro de L. Suponga que xz es miembro de L y wz no es miembro de L. xz ∈ L implica yz ∈ L. wz ∉ L implica que yz ∉ L. Esto es una contradicción ya que yz no puede ser miembro y no ser miembro de L. Por lo tanto, x ≡ L y y y ≡ L w ⇒ x ≡ L w.
Dado que ≡ L es una relación de equivalencia sobre ∑*, ≡ L divide ∑* en conjuntos disjuntos llamados clases de equivalencia.
Teorema de Myhill Nerode:
Un lenguaje es regular si y solo si ≡ L divide ∑* en un número finito de clases de equivalencia. Si ≡ L divide ∑* en n clases de equivalencia, entonces un DFA mínimo que reconoce L tiene exactamente n estados.
Ejemplo :
Para demostrar que L = {a n b n | n ≥ 0} no es regular.
Podemos demostrar que L tiene infinitas clases de equivalencia mostrando que ak y ai son distinguibles por L siempre que k ≠ i. Así, para x = ak y y = ai hacemos que z = bk . Entonces xz = a k b k está en el lenguaje pero yz = a i b k no lo está. Por lo tanto, cada clase de equivalencia de L puede contener como máximo una string de la forma a i , por lo que debe haber infinitas clases de equivalencia. Eso significa que L no es regular según el teorema de Myhill Nerode.
Nota: Para probar si un lenguaje L es regular o no, también se hace usando el lema de bombeo, la distinción entre este y el teorema de Myhill Nerode es que hay algunos lenguajes no regulares que satisfacen el lema de bombeo, pero no existe tal lenguaje no regular que satisface el teorema de Myhill Nerode.