Teorema de Myhill-Nerode

Condición necesaria y suficiente para que un lenguaje formal sea regular

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

Declaración

Dado un lenguaje , y un par de cadenas y , defina una extensión distintiva como una cadena tal que exactamente una de las dos cadenas y pertenece a . Defina una relación en cadenas como si no hubiera una extensión distintiva para y . Es fácil demostrar 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 \sim _{L}}$ ${\displaystyle x\;\sim _{L}\ y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \sim _{L}}$

El teorema de Myhill-Nerode establece que un lenguaje 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 autómata finito determinista (AFD) mínimo que acepta . Además, todo AFD mínimo para el lenguaje es isomorfo al canónico (Hopcroft y Ullman 1979). ${\displaystyle L}$ ${\displaystyle \sim _{L}}$ ${\displaystyle L}$

Myhill, Nerode (1957)  —  (1) es regular si y sólo si tiene un número finito de clases de equivalencia. ${\displaystyle L}$ ${\displaystyle \sim _{L}}$

(2) Este número es igual al número de estados en el autómata finito determinista mínimo (DFA) que acepta . ${\displaystyle L}$

(3) Cualquier aceptor DFA mínimo para el lenguaje es isomorfo al siguiente:

Sea cada clase de equivalencia correspondiente a un estado, y sean las transiciones de estado para cada . Sea el estado inicial y los estados de aceptación donde . ${\displaystyle [x]}$ ${\displaystyle a:[x]\to [xa]}$ ${\displaystyle a\in \Sigma }$ ${\displaystyle [\epsilon ]}$ ${\displaystyle [x]}$ ${\displaystyle x\in L}$

En general, para cualquier lenguaje, el autómata construido es un autómata que acepta 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 se refieren a la relación como congruencia de Nerode , ^{[1] [2]} en honor a Anil Nerode . ${\displaystyle \sim _{L}}$

Prueba

(1) Si es regular, construya un DFA mínimo para aceptarlo. Claramente, si terminan en el mismo estado después de ejecutar el DFA, entonces , por lo tanto, el número de clases de equivalencia de es como máximo el número de estados del DFA, que debe ser finito. ${\displaystyle L}$ ${\displaystyle x,y}$ ${\displaystyle x\sim _{L}y}$ ${\displaystyle \sim _{L}}$

Por el contrario, si tiene un número finito de clases de equivalencia, entonces el autómata de estado construido en el teorema es un aceptor de DFA, por lo tanto el lenguaje es regular. ${\displaystyle \sim _{L}}$

(2) Por la construcción en (1).

(3) Dado un aceptor DFA mínimo , construimos un isomorfismo al canónico. ${\displaystyle A}$

Construya la siguiente relación de equivalencia: si y solo si terminan en el mismo estado al ejecutarse a través de . ${\displaystyle x\sim _{A}y}$ ${\displaystyle x,y}$ ${\displaystyle A}$

Dado que es un aceptor, si entonces . Por lo tanto, cada clase de equivalencia es una unión de una o más clases de equivalencia de . Además, dado que es mínimo, el número de estados de es igual al número de clases de equivalencia de por la parte (2). Por lo tanto . ${\displaystyle A}$ ${\displaystyle x\sim _{A}y}$ ${\displaystyle x\sim _{L}y}$ ${\displaystyle \sim _{L}}$ ${\displaystyle \sim _{A}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \sim _{L}}$ ${\displaystyle \sim _{A}=\sim _{L}}$

Ahora bien, esto nos da una biyección entre los estados de 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 DFA. ${\displaystyle A}$

Uso y consecuencias

El teorema de Myhill-Nerode puede utilizarse para demostrar que un lenguaje es regular , demostrando que el número de clases de equivalencia de es finito. Esto puede hacerse mediante un análisis exhaustivo de casos 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, (o ), , y son extensiones distintivas que dan como resultado las tres clases (que corresponden 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 extensiones distintivas. El autómata mínimo que acepta nuestro lenguaje tendría tres estados correspondientes a estas tres clases de equivalencia. ${\displaystyle L}$ ${\displaystyle \sim _{L}}$ ${\displaystyle 00}$ ${\displaystyle 11}$ ${\displaystyle 01}$ ${\displaystyle 10}$

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

Generalizaciones

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

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

Referencias

1. Brzozowski, Janusz ; Szykuła, Marek; Ye, Yuli (2018), "Complejidad sintáctica de los ideales regulares", Teoría de los sistemas informáticos , 62 (5): 1175–1202, doi :10.1007/s00224-017-9803-8, hdl : 10012/12499 , S2CID  2238325
2. Crochemore, Maxime; et al. (2009), "De la congruencia de Nerode a los autómatas de sufijo con desajustes", Theoretical Computer Science , 410 (37): 3471–3480, doi : 10.1016/j.tcs.2009.03.011 , S2CID  14277204
3. Hubert Comon; Max Dauchet; Rémi Gilleron; Florent Jacquemard; Denis Lugiez; Christoph Löding; Sophie Tison; Marc Tommasi (octubre de 2021). Técnicas y aplicaciones de autómatas de árboles (TATA).Aquí: Sect. 1.5, p.35-36.

• Hopcroft, John E. ; Ullman, Jeffrey D. (1979), "Capítulo 3.4", Introducción a la teoría de autómatas, lenguajes y computación , Reading, Massachusetts: Addison-Wesley Publishing, ISBN 0-201-02988-X.
• Nerode, Anil (1958), "Transformaciones de autómatas lineales", Actas de la American Mathematical Society , 9 (4): 541–544, doi : 10.1090/S0002-9939-1958-0135681-9 , JSTOR  2033204.
• Nerode, Anil; Sauer, Burton P. (noviembre de 1957), Conceptos fundamentales en la teoría de sistemas (informe técnico de WADC), Wright Air Development Center. Documento ASTIA N° AD 155741.
• Regan, Kenneth (2007), Notas sobre el teorema de Myhill-Nerode (PDF) , consultado el 22 de marzo de 2016.

Lectura adicional

• Bakhadyr Khoussainov; Anil Nerode (6 de diciembre de 2012). Teoría de autómatas y sus aplicaciones. Springer Science & Business Media. ISBN 978-1-4612-0171-7.