Teorema de Myhill-Nerode

Teorema de Myhill-Nerode
Myhill-Nerode
Teorema de Myhill-Nerode:
Sea L* un lenguaje y sea u L v definida como antes.
Entonces L es regular ssi L es de índice finito.
Demostración:
(, La dirección fácil )
•L es regular   AFD M=(Q, , , q0, F), L=L(M)
 el índice de M es |Q|.
•Como cada clase de equivalencia de L está formada por
una o más clases de equivalencia de M, el índice de L
debe ser |Q| o menor.
Myhill-Nerode
Teorema de Myhill-Nerode:
Sea L* un lenguaje y sea u L v definida como antes.
Entonces L es regular ssi L es de índice finito.
Demostración:
() Definimos el AFD M=(Q, , , q0, F) mediante
•Q = */L, [el conjunto de clases de equivalencia de L ]
•q0 = []
•F = { qQ: qL}
•( [u], ) = [u]
PDQ: L(M)=L. Además veremos que M es mínimo.

Myhill-Nerode
Q = */L, [conjunto de clases de equivalencia de L ]
q0 = [], F = { qQ: qL}, ( [u], ) = [u]
PDQ L(M)=L.
Es decir, que u*, uL(M)  [u]L
Pero uL(M)  (q0,u)F  ([],u)L

así que estamos listos si demostramos que ([],u)=[u].
Demostraremos, más en general, que

u,v*, ([v],u)=[vu]
Myhill-Nerode
q0 = [], F = { qQ: qL}, ( [u], ) = [u]
PDQ u,v*, ([v],u)=[vu]
Inducción sobre |u| :

Base:
|u|=1. Cierto, por definición de .
Paso inductivo:
|u|>1, u=w para algún , w con |w|<|u|.
([v],u) = ([v],w) = (([v],w),) = ([vw],) = [vw] = [vu]
Definición Hipótesis de Definición

(recursiva) de  inducción de 
Myhill-Nerode
q0 = [], F = { qQ: qL}, ( [u], ) = [u]
Lo único que falta ver es que M es mínimo. Recordemos

que sus estados son las clases de equivalencia de L.
 Para cada par de estados [u], [v], existe una

palabra w que distingue las clases de equivalencia (si
no, serían la misma clase).
 uw y vw están una fuera y la otra dentro de L.
 [uw] y [vw] están uno fuera y otro dentro de F.
w también distingue los estados correspondientes.
QED
Myhill-Nerode
¿Cuál es la intuición tras Myhill-Nerode?

•Recibimos el input: u=vw
•Al terminar de verlo, debemos decidir
acaso uL.
•Hemos leído v, falta w.
•La relación L está definida de tal forma que lo único

que necesitamos saber (para cumplir con la tarea final)
es en cuál clase de equivalencia está v.
Myhill-Nerode
0
1 [v]
•La función  define como voy
actualizando esa información con
cada nueva letra que pasa. [v1] [v0]
•Myhill-Nerode lo que me dice es que

un lenguaje es regular ssi eso que
tengo que saber, momento a momento,
cabe en una memoria finita.
La unicidad del AFD mínimo.
Teorema de minimización:
Sea L un lenguaje regular. Entonces dentro de los AFD que
reconocen a L, existe un único AFD que tiene la cantidad mínima
de estados, y es el que se obtiene a partir de cualquier otro
mediante la aplicación del algoritmode minimización.
Supongamos que partimos de dos AFD distintos,
ambos con el mismo lenguaje, y llegamos a dos AFD
minimales M y M’.
¿Qué significa que sean el mismo?

Significa que salvo “cambio de nombre”, los estados
son los mismos. Llamemos  al cambio de nombre.
0
 1
q 0
0 0 B
1 A
q1 0
1 0 1
q11 -1 1
C
1
Dados dos AFD M=(Q, , , q0, F) y M’=(Q’, , ’, q’0,
F’), son “el mismo” ssi existe :QQ’ biyectiva tal que
• (q0) = q’0  es un isomorfismo

• (F) = F’ entre M y M’.
• ((q,)) = ((q),)
En el ejemplo de abajo, (q)=A, (q11)=B, (q1)=C.

0
 1
q 0
0 0 B
1 A
q1 0
1 0 1
q11 -1 1
C
1
•Ser isomorfos (“ser el mismo”) es claramente una

relación de equivalencia entre AFD.
Para probar que dos AFD son isomorfos, sirve
probar que ambos son isomorfos a un tercero.
Usando Myhill-Nerode
Myhill-Nerode sirve por lo tanto para explicar el

algoritmo de minimización y su resultado.
Sin embargo, también se puede usar directamente,

como herramienta para demostrar que un cierto
lenguaje NO es regular.
Problemas de decisión para LR
Sea L un lenguaje regular, que conocemos de alguna
forma (ER, AFND, descripción verbal...).
Hay varias preguntas típicas que interesa poder
contestar; a continuación, veremos formas de
contestarlas.
Dada una palabra w, ¿wL?
Respuesta: construimos el AFD para L, y

vemos si acepta w.
¿L  ?
Respuesta 1: construimos el AF (sirven D y ND)

para L, y vemos acaso existe un camino desde q0
hasta algún qF. Para eso podemos usar los
algoritmos de recorrido de grafos vistos es EDA.
Otra forma: si el AF tiene K estados, podemos

hacer la prueba con todas las palabras de largo 
K. Si ninguna de esas se acepta, entonces L=.
[¿Razón de eso? Lema de bombeo!]
¿L  ? Ojo: recordar en este contexto que  es una palabra:
si lo que nos queda es , entonces no es vacío.
Respuesta 2: construimos una ER para L. Desde ahí

es fácil encontrar alguna palabra de L.
•Borramos las *
•En cada “+”, eliminamos un lado (si alguno es ,
borramos ese; si no, borramos cualquiera, p.ej., el
lado derecho).
•Borramos los paréntesis.
Lo que queda [ejercicio] es una palabra de L.
r = (a+)(ab*+ba*)*(+b*)*
 (a+)(ab+ba)(+b)  (a)(ab)()  aab  L(r)
Recordar que eso significa:
¿Es L infinito? “¿Contiene L una cantidad
infinita de palabras?”
Respuesta 1: Construimos un AFD para L, y vemos

acaso existe un camino desde q0 hasta algún qF que
incluya algún ciclo.
También es EDA: Borramos
todo lo que no sea
alcanzable desde q0, y
también todo lo que no sea
alcanzable desde F
Nota: Funciona con AFND+, siguiendo arcos al revés.
pero no se consideran los ciclos En lo que queda, vemos
formados por transiciones . acaso hay ciclos.
¿Es L infinito?
Respuesta 2:
•Sea M un AFD de n estados que reconoce L.
•L es infinito ssi reconoce alguna palabra de largo
n  m  2n
Por lo tanto, podemos probar todas esas, et voilà.
Razón de que eso sea cierto: ejercicio. Pero también es vía

bombeo.
Dados dos lenguajes regulares L1 y L2. ¿Son iguales?
Respuesta 1:
•Construimos un AFD para cada uno.
•Los minimizamos.
•Vemos si los AFD resultantes son isomorfos.
Respuesta 2:
•Ver acaso L1L2 =  A\B AB
L1L2 = (L1\L2)  (L2\L1) = (L1L2C)  (L1CL2) ]
 Es regular y podemos construirle un AFD, según vimos en las
propiedades de clausura. Luego aplicamos lo de la transparencia 173.
Problemas “decidibles”
Las preguntas previas tienen algo en común: todas
piden una respuesta del tipo sí/no.
Se habla de problemas de decisión.
Si existe un algoritmo para resolver un problema

de decisión, decimos que el problema es decidible.
Por lo tanto decimos que los problemas anteriores

son decidibles para lenguajes regulares.
Más adelante veremos que, para otras clases de

lenguajes, pueden ser indecidibles.

Teorema de Myhill-Nerode

Cargado por

Copyright:

Formatos disponibles

Teorema de Myhill-Nerode

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Teorema de Myhill-Nerode

Cargado por

Copyright:

Formatos disponibles

Teorema de Myhill-Nerode

PDQ: L(M)=L. Además veremos que M es mínimo.

Es decir, que u*, uL(M)  [u]L

Pero uL(M)  (q0,u)F  ([],u)L

Demostraremos, más en general, que

Inducción sobre |u| :

([v],u) = ([v],w) = (([v],w),) = ([vw],) = [vw] = [vu]

Definición Hipótesis de Definición

Lo único que falta ver es que M es mínimo. Recordemos

 Para cada par de estados [u], [v], existe una

w también distingue los estados correspondientes.

¿Cuál es la intuición tras Myhill-Nerode?

•La relación L está definida de tal forma que lo único

•Myhill-Nerode lo que me dice es que

¿Qué significa que sean el mismo?

• (q0) = q’0  es un isomorfismo

En el ejemplo de abajo, (q)=A, (q11)=B, (q1)=C.

•Ser isomorfos (“ser el mismo”) es claramente una

Myhill-Nerode sirve por lo tanto para explicar el

Sin embargo, también se puede usar directamente,

Dada una palabra w, ¿wL?

Respuesta: construimos el AFD para L, y

Respuesta 1: construimos el AF (sirven D y ND)

Otra forma: si el AF tiene K estados, podemos

Respuesta 2: construimos una ER para L. Desde ahí

Respuesta 1: Construimos un AFD para L, y vemos

Razón de que eso sea cierto: ejercicio. Pero también es vía

Se habla de problemas de decisión.

Si existe un algoritmo para resolver un problema

Por lo tanto decimos que los problemas anteriores

Más adelante veremos que, para otras clases de

También podría gustarte