C5 ¡El gato Tacocat, que puede escribir letras minúsculas del inglés así como huellas $\star$ , desea identificar palíndromos! Sea $S=\{a,b,\dots,z\}$ el conjunto de las letras del inglés, y defina $T=S\cup \{\star\}$ . Tacocat tiene una lista de palabras $(w_1, u_1)$ , $\dots$ , $(w_n, u_n)$ , formadas por caracteres de $T$ . Un humano le da a Tacocat una cadena $s$ de letras de $S$ , a la cual Tacocat antepone dos huellas a la izquierda de la cadena, creando $s'$ . Luego, Tacocat repite lo siguiente hasta que ninguna de $w_1$ , $\dots$ , $w_n$ sea una subcadena de $s'$ : Para el menor $i$ tal que $w_i$ es una subcadena de $s'$ , la primera aparición de $w_i$ es reemplazada por $u_i$ . ¿Puede Tacocat elegir palabras $w_i$ y $u_i$ , y una palabra $W$ , formada por letras de $T$ , de modo que el proceso termine para toda $s$ , y la palabra final sea $W$ si y solo si la cadena original $s$ era un palíndromo? Karn Chutinan