Hola,
No me queda claro como resolver esta parte del ejercicio, ya que la solucion afirma que el lenguaje es regular, pero las tiras son de la forma xwyx, con "x" perteneciente a un lenguaje finito, "w" pertenece a un lenguaje regular e "y" pertenece al reverso del lenguaje anterior. Mi duda de si es regular es porque se impone que x es la misma, no encuentro un automata o ER que reconozca esto.
Muchas gracias.
hola:
el problema de verificar que dos subtiras son iguales, en el caso general, no se resuelve con un AFD: uno debería guardar en memoria una tira completa para verificarla contra la otra. como la única memoria que se tiene son los estados y la cantidad de tiras es infinita, la cantidad de estados que se necesitarían para recordar una tira cualquiera también sería infinita. el punto en este ejercicio es que el lenguaje es finito y, por lo tanto, se puede recordar a todas las tiras posibles utilizando una cantidad finita de estados.
análogamente, no se puede en general reconocer a una tira y a su reverso. sin embargo, en este caso w e y no son "reversos" uno del otro, sino que pertenecen a los lenguajes reversos, con lo cual no preciso recordar una tira para verificarla respecto a la otra. por ejemplo, para los lenguajes L(a*b) y L(ba*)=L(a*b)^R, w podría ser aaaab e y ser ba.
saludos,
d.-