Proposición 6.1 (Teorema de Myhill-Nerode)
Sea
un lenguaje arbitrario. Las siguientes aseveraciones son equivalentes a pares:
- 1.
- L es regular.
- 2.
- L es la unión de algunas clases de equivalencia de una relación de equivalencia de índice finito, congruente por la derecha con la concatenación de palabras.
- 3.
- La relación
tal que
es una relación de índice finito.