Coding the Impossible: Palindrome Detector with a Regular Expressions

Of course, we should distinguish regexen that include extensions like back references, from formal regular expressions.

The given technique works for finite palindromes using regexen that support back references. If we want to use a formal regular expression to recognize finite palindromes...

Any language that has a finite number of sentences, and is composed of strings of a finite length, can be recognized by a formal regular expression.

Worst case, we can brute force it by making a big union of strings in the language.

This applies to palindromes of a fixed length iff the alphabet of our language is finite.

e.g., if our alphabet is the second smallest (0|1), then recognizers for palindromes of length 1, 2, 3, 4... are:

  0|1
  00|11
  000|010|101|111
  0000|0110|1001|1111
  ...