Teorema de Myhill-Nerode

En la teoría de los lenguajes formales, el teorema de Myhill-Nerode define una condición necesaria y suficiente para la regularidad de un lenguaje.

El teorema lleva el nombre de John Myhilly Anil Nerodequien lo demostró en la Universidad de Chicago en 1958 . [una]

Enunciado del teorema

Sea un idioma en el alfabeto y se dé una relación de palabras del conjunto de todas las palabras en el alfabeto dado tal que si y solo si para todas las que pertenecen al conjunto de todas las palabras en el alfabeto dado, ambas palabras y pertenecen simultáneamente oa la vez no pertenecen a la lengua . Es fácil probar que es una relación de equivalencia sobre el conjunto de palabras del alfabeto . $L$ $V$ ${\ estilo de visualización \ equiv _ {L}}$ $x\equiv _{L}y$ $z$ ${\ estilo de visualización xz}$ ${\ estilo de visualización yz}$ $L$ ${\ estilo de visualización \ equiv _ {L}}$ $V$

Por el teorema de Myhill-Nerode, el número de estados en un autómata finito determinista mínimo (DFA) que acepta un lenguaje es igual al número de clases de equivalencia con respecto a , es decir, la potencia del conjunto factorial del lenguaje con respecto a . Este número también se denomina índice de una relación binaria y se denota como . $L$ ${\ estilo de visualización \ equiv _ {L}}$ $L$ ${\ estilo de visualización \ equiv _ {L}}$ $ind\equiv _{L}$

Prueba

Consecuencias

Del teorema de Myhill-Nerode se deduce que una lengua es regular si y sólo si el número de clases de equivalencia es finito. Uno puede concluir inmediatamente que si la relación divide el lenguaje en un número infinito de clases de equivalencia, entonces el lenguaje no es regular. Esta conclusión se utiliza muy a menudo para probar la irregularidad de las lenguas. $L$ ${\ estilo de visualización \ equiv _ {L}}$ ${\ estilo de visualización \ equiv _ {L}}$ $L$ $L$

Véase también

Lema de crecimiento

Notas

↑ A. Nerode, "Transformaciones de autómatas lineales", Proceedings of the AMS , 9 (1958) pp 541-544.

Literatura

Tom Henzinger, Conferencia 7: Teorema de Myhill-Nerode (2003)
El teorema de Myhill-Nerode (apuntes de clases de la asignatura "Teoría e Implementación de Lenguajes de Programación", FUPM MIPT).

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami