Teorema de Myhill-Nerodo

Condición necesaria y suficiente para que una lengua formal sea regular

En la teoría de las lenguas formales , el teorema de Myhill-Nerode proporciona una condición necesaria y suficiente para que una lengua sea regular . El teorema lleva el nombre de John Myhill y Anil Nerode , quienes lo demostraron en la Universidad de Chicago en 1957 (Nerode y Sauer 1957, p. ii).

Declaración

Dado un idioma y un par de cadenas y , defina una extensión distintiva como una cadena tal que exactamente una de las dos cadenas 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 mínimo (DFA) que acepta . Además, cada DFA mínimo para la lengua 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 aceptador mínimo de DFA para el idioma es isomorfo al siguiente:

Deje que cada clase de equivalencia corresponda a un estado y que las transiciones de estado sean para cada uno . 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}$

Generalmente, para cualquier idioma, el autómata construido es un aceptador de autómata de estado . 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 termina en el mismo estado después de pasar por 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 que el lenguaje es regular. ${\displaystyle \sim _{L}}$

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

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

Construya la siguiente relación de equivalencia: si y solo si terminan en el mismo estado cuando se ejecuta . ${\displaystyle x\sim _{A}y}$ ${\displaystyle x,y}$ ${\displaystyle A}$

Puesto que es un aceptor, si entonces . Por tanto, cada clase de equivalencia es una unión de una o más clases de equivalencia de . Además, como es mínimo, el número de estados de es igual al número de clases de equivalencia de la parte (2). De este modo . ${\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. Está 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 se puede utilizar para demostrar que una lengua es regular demostrando que el número de clases de equivalencia es finito. Esto se puede hacer mediante un análisis de caso exhaustivo en el que, comenzando desde 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 se pueden dividir por 3 es regular. Dada la cadena vacía, (o ), y son extensiones distintivas que dan como resultado las tres clases (correspondientes a números que dan restos 0, 1 y 2 cuando se dividen por 3), pero después de este paso ya no hay extensión distintiva. El autómata mínimo que aceptara 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 idioma la relación tiene infinitas clases de equivalencia, no es regular. Es este corolario el que se utiliza frecuentemente para demostrar que una lengua no es regular. ${\displaystyle L}$ ${\displaystyle \sim _{L}}$

Generalizaciones

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

Ver también

• Lema de bombeo para lenguajes regulares , un método alternativo para demostrar que un lenguaje no es regular. Es posible que el lema del bombeo no siempre pueda 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 con sufijos con discrepancias", Ciencias de la Computación Teórica , 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í: Secc. 1.5, págs.35-36.

• Hopcroft, John E .; Ullman, Jeffrey D. (1979), "Capítulo 3.4", Introducción a la teoría, los lenguajes y la computación de los autómatas , Reading, Massachusetts: Addison-Wesley Publishing, ISBN 0-201-02988-X.
• Nerode, Anil (1958), "Transformaciones de autómatas lineales", Actas de la Sociedad Matemática Estadounidense , 9 (4): 541–544, doi : 10.1090/S0002-9939-1958-0135681-9 , JSTOR  2033204.
• Nerodo, Anil; Sauer, Burton P. (noviembre de 1957), Conceptos fundamentales en la teoría de sistemas (Informe técnico 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.

Otras lecturas

• Bakhadyr Khoussainov; Anil Nerode (6 de diciembre de 2012). Teoría de los autómatas y sus aplicaciones. Medios de ciencia y negocios de Springer. ISBN 978-1-4612-0171-7.