How to check that a string is a palindrome using regular expressions?

by

The answer to this question is that “it is impossible”. More specifically, the interviewer is wondering if you paid attention in your computational theory class.

In your computational theory class you learned about finite state machines. A finite state machine is composed of nodes and edges. Each edge is annotated with a letter from a finite alphabet. One or more nodes are special “accepting” nodes and one node is the “start” node. As each letter is read from a given word we traverse the given edge in the machine. If we end up in an accepting state then we say that the machine “accepts” that word.

A regular expression can always be translated into an equivalent finite state machine. That is, one that accepts and rejects the same words as the regular expression (in the real world, some regexp languages allow for arbitrary functions, these don’t count).

It is impossible to build a finite state machine that accepts all palindromes. The proof relies on the facts that we can easily build a string that requires an arbitrarily large number of nodes, namely the string

a^x b a^x (eg., aba, aabaa, aaabaaa, aaaabaaaa, ….)

where a^x is a repeated x times. This requires at least x nodes because, after seeing the ‘b’ we have to count back x times to make sure it is a palindrome.

Finally, getting back to the original question, you could tell the interviewer that you can write a regular expression that accepts all palindromes that are smaller than some finite fixed length. If there is ever a real-world application that requires identifying palindromes then it will almost certainly not include arbitrarily long ones, thus this answer would show that you can differentiate theoretical impossibilities from real-world applications. Still, the actual regexp would be quite long, much longer than equivalent 4-line program (easy exercise for the reader: write a program that identifies palindromes).

More Related Contents:

  1. Reg-ex to validate a sting with digits only but all Zeros are not allowed [closed]
  2. Regular expression to remove fancy apostrophe [closed]
  3. Why doesn’t [01-12] range work as expected?
  4. Regular expression for a string containing one word but not another
  5. How do I use regex in a SQLite query?
  6. Replace single backslash in R
  7. How to use regex with find command?
  8. How can I recognize an evil regex?
  9. What is the best regular expression to check if a string is a valid URL?
  10. Using regexes, how to efficiently match strings between double quotes with embedded double quotes?
  11. How to detect a floating point number using a regular expression
  12. RegEx for both, integer and float [closed]
  13. powershell: how to escape all regex characters from a string
  14. Regex to disallow more than 1 dash consecutively
  15. Is it possible for a computer to “learn” a regular expression by user-provided examples?
  16. Regex, every non-alphanumeric character except white space or colon
  17. How .* (dot star) works? [closed]
  18. How do you extract IP addresses from files using a regex in a linux shell?
  19. Why is this regex using lookbehinds invalid in R?
  20. Fully qualified domain name validation
  21. Using positive-lookahead (?=regex) with re2
  22. apache HTTP:X-Forwarded-Proto in .htaccess is causing redirect loop in dev environment
  23. Regular expression limit string size
  24. JavaScript: split doesn’t work in IE?
  25. Does lookaround affect which languages can be matched by regular expressions?
  26. Overlapping matches in R
  27. Redirect all traffic to root of another domain
  28. ignoring changes matching a string in git diff
  29. ElasticSearch and Regex queries
  30. Regex allow digits and a single dot

Leave a Comment