Comment vérifier qu'une chaîne de caractères est un palindrome à l'aide d'expressions régulières ?

Question

C'était une question d'entretien à laquelle je n'ai pas pu répondre :

Comment vérifier qu'une chaîne de caractères est un palindrome à l'aide d'expressions régulières ?

p.s. Il y a déjà une question " Comment vérifier si la chaîne de caractères donnée est palindrome ? "et cela donne beaucoup de réponses dans différentes langues, mais aucune réponse qui utilise des expressions régulières.

Answer 1

La réponse à cette question est "c'est impossible". Plus précisément, l'enquêteur se demande si vous avez été attentif dans votre cours de théorie computationnelle.

Dans votre cours de théorie informatique, vous avez appris les machines à états finis. Une machine à états finis est composée de nœuds et d'arêtes. Chaque arête est annotée d'une lettre d'un alphabet fini. Un ou plusieurs nœuds sont des nœuds spéciaux "acceptants" et un nœud est le nœud "de départ". Au fur et à mesure que chaque lettre est lue dans un mot donné, nous traversons l'arête donnée dans la machine. Si nous arrivons dans un état d'acceptation, nous disons que la machine "accepte" ce mot.

Une expression régulière peut toujours être traduite en une machine à états finis équivalente. C'est-à-dire une machine qui accepte et rejette les mêmes mots que l'expression régulière (dans le monde réel, certains langages regexp autorisent des fonctions arbitraires, mais celles-ci ne comptent pas).

Il est impossible de construire une machine à états finis qui accepte tous les palindromes. La preuve repose sur le fait que nous pouvons facilement construire une chaîne qui nécessite un nombre arbitrairement grand de nœuds, à savoir la chaîne

a^x b a^x (par exemple, aba, aabaa, aaabaaa, aaaabaaaa, ....)

où a^x est a répété x fois. Cela nécessite au moins x nœuds car, après avoir vu le "b", nous devons compter x fois en arrière pour nous assurer qu'il s'agit bien d'un palindrome.

Enfin, pour en revenir à la question initiale, vous pourriez dire à votre interlocuteur que vous pouvez écrire une expression régulière qui accepte tous les palindromes dont la taille est inférieure à une longueur fixe finie. S'il existe un jour une application du monde réel nécessitant l'identification de palindromes, il est presque certain qu'elle n'inclura pas les palindromes de longueur arbitraire. Cette réponse montrerait donc que vous pouvez faire la différence entre les impossibilités théoriques et les applications du monde réel. Néanmoins, la regexp réelle serait assez longue, bien plus longue que le programme équivalent de 4 lignes (exercice facile pour le lecteur : écrire un programme qui identifie les palindromes).

Answer 2

Alors que le PCRE prend en charge les expressions régulières récursives (voir la réponse de Peter Krauss ), vous ne pouvez pas utiliser une regex sur l'option UNITÉ DE SOINS INTENSIFS (comme celui utilisé, par exemple, par Apple) pour y parvenir sans code supplémentaire. Vous devrez faire quelque chose comme ceci :

Cela détecte tout palindrome, mais nécessite une boucle (qui sera nécessaire car les expressions régulières ne peuvent pas compter).

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";

Answer 3

Ce n'est pas possible. Les palindromes ne sont pas définis par un langage régulier. (Vous voyez, j'ai vraiment appris quelque chose en théorie informatique)

Answer 4

Avec Perl regex :

/^((.)(?1)\2|.?)$/

Cependant, comme beaucoup l'ont fait remarquer, cela ne peut pas être considéré comme une expression régulière si l'on veut être strict. Expressions régulières ne supporte pas la récursion.

Answer 5

Voici un pour détecter les palindromes de 4 lettres (ex : deed), pour tout type de caractère :

\(.\)\(.\)\2\1

Voici un pour détecter les palindromes à 5 lettres (ex : radar), en vérifiant uniquement les lettres :

\([a-z]\)\([a-z]\)[a-z]\2\1

Il semble donc que nous ayons besoin d'une regex différente pour chaque longueur de mot possible. Ce poste sur une liste de diffusion Python comprend quelques détails sur le pourquoi (Finite State Automata and pumping lemma).