Supongamos que h es un homomorfismo que pasa del alfabeto {0,1,2} al alfabeto {a,b} y se define así: h(0) = a; h(1) = ab y h(2) = ba.
a) Qué es h(0120)? aabbaa
b) Qué es h(21120)? baababbaa
c) Si L es el lenguaje L(01^*2), qué es h(L)? El lenguaje de la expresión regular a(ab)^*ba
d) Si L es e lenguaje L(0+12), Qué es h(L)? El lenguaje descrito por a + abba
a) Qué es h(0120)? aabbaa
b) Qué es h(21120)? baababbaa
c) Si L es el lenguaje L(01^*2), qué es h(L)? El lenguaje de la expresión regular a(ab)^*ba
d) Si L es e lenguaje L(0+12), Qué es h(L)? El lenguaje descrito por a + abba
e) Supongamos que L es el lenguaje {ababa}, es decir, el que sólo contiene la cadena ababa. Qué es h^(-1)(L)? "Cada b debe provenir de 1 o 2. Sin embargo, si el primer b viene de 2 y el segundo de 1, entonces ambos van a necesitar la a entre ellos como parte de h(2) y h(1) respectivamente. Así que el homomorfismo inverso consiste de las cadenas {110, 102, 022}" (Traducido desde http://infolab.stanford.edu/~ullman/ialcsols/sol4.html).
f) h^(-1)(L) con L(a(ba)^*) debe ser el conjunto descrito por 02^* + (1^*0)^*2^*. Será esta una descripción redundante?
0 comentarios:
Publicar un comentario