Solución:
La respuesta a esta pregunta es que “es imposible”. Más específicamente, el entrevistador se pregunta si prestó atención en su clase de teoría computacional.
En su clase de teoría computacional aprendió acerca de las máquinas de estados finitos. Una máquina de estados finitos se compone de nodos y aristas. Cada borde está anotado con una letra de un alfabeto finito. Uno o más nodos son nodos de “aceptación” especiales y un nodo es el nodo de “inicio”. A medida que se lee cada letra de una palabra dada, atravesamos el borde dado en la máquina. Si terminamos en un estado de aceptación, decimos que la máquina “acepta” esa palabra.
Una expresión regular siempre se puede traducir a una máquina de estados finitos equivalente. Es decir, uno que acepta y rechaza las mismas palabras que la expresión regular (en el mundo real, algunos lenguajes de expresiones regulares permiten funciones arbitrarias, estas no cuentan).
Es imposible construir una máquina de estados finitos que acepte todos los palíndromos. La prueba se basa en los hechos de que podemos construir fácilmente una cadena que requiera una cantidad arbitrariamente grande de nodos, es decir, la cadena
a ^ xba ^ x (p. ej., aba, aabaa, aaabaaa, aaaabaaaa, ….)
donde a ^ x es un x repetido. Esto requiere al menos x nodos porque, después de ver la ‘b’, tenemos que contar hacia atrás x veces para asegurarnos de que sea un palíndromo.
Finalmente, volviendo a la pregunta original, podría decirle al entrevistador que puede escribir una expresión regular que acepte todos los palíndromos que sean más pequeños que una longitud fija finita. Si alguna vez existe una aplicación del mundo real que requiera identificar palíndromos, es casi seguro que no incluirá los que son arbitrariamente largos, por lo que esta respuesta mostraría que puede diferenciar las imposibilidades teóricas de las aplicaciones del mundo real. Aún así, la expresión regular real sería bastante larga, mucho más larga que el programa equivalente de 4 líneas (ejercicio fácil para el lector: escriba un programa que identifique palíndromos).
Si bien el motor PCRE admite expresiones regulares recursivas (consulte la respuesta de Peter Krauss), no puede usar una expresión regular en el motor ICU (como lo usa, por ejemplo, Apple) para lograr esto sin código adicional. Deberá hacer algo como esto:
Esto detecta cualquier palíndromo, pero requiere un bucle (que será necesario porque las expresiones regulares no pueden contar).
$a = "teststring";
while(length $a > 1)
{
$a =~ /(.)(.*)(.)/;
die "Not a palindrome: $a" unless $1 eq $3;
$a = $2;
}
print "Palindrome";
No es posible. Los palíndromos no están definidos por un lenguaje regular. (Mira, aprendí algo en teoría computacional)