2

Can regexp pattern matching be used to check for palindromes within a given text in Java?

My intuition is that in order to check for palindromes, we may need to remember the character that was parsed, which cannot be done using regexp. Is that correct?

  • 1
    @OliverWeiler but the recurse isn't available in the java regex – ratchet freak Aug 21 '14 at 16:33
  • 6
    No, for a regex to be able to check a language (in this case the language of palindromes) the language needs to be a regular language – ratchet freak Aug 21 '14 at 16:39
  • 2
    Just to add, Perl's regular expression is more powerful than what is usually understood as such. So the answer is no, you can't check for palindromes with regular expressions. – Phil Aug 21 '14 at 16:40
  • 4
    This question appears to be off-topic because it would be better asked on Stack Overflow. If migrated to SO, this question would likely be closed as a duplicate of stackoverflow.com/questions/22349358/… – GlenH7 Aug 21 '14 at 16:58
  • 1
    I'd have to ask why you'd want to - just compare the reverse of the string with the string. In most languages this will be quicker to execute, and quicker to write surely? Use regexes for what they are good for. – David Scholefield Aug 21 '14 at 17:04
5

First off, when you start poking around with questions like this, you will mix the aspects of Computer Science and what is actually out there. Computer Science considers a regular expression different than what perl m// or java.util.regex can do.

This is the Apocalypse on Pattern Matching, generally having to do with what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood).

Larry wall from Apocalypse 5, June 4th, 2002

What exists in regex as we programmers know them is a significant superset of what traditional finite automata can do (that's a fun paper to read if you like the science part of CS).

The thing that this question boils down to is the pumping lemma on regular languages. This can be said that if you have a regular language, you can put things into the middle without changing if the language is accepted.

Consider a language of binary palindromes. It matches 101. It also matches 1001 and 10001 and so forth. You can put as many things in the middle there without changing if it should be accepted. If its regular, it will handle 10101010101010101 and so on.

However, a regular expression is just short hand for writing a finite automata. The word finite is key. It has a finite number of states. This means that if I put enough things in that word to be tested, it will repeat the same state twice if there are more elements to it than there are states (this is the pigeonhole principle). Once that happens, the state of the automata will get confused and either generate a false positive or a false negative... and thus, using the pumping lemma, it can be shown that a language containing palindromes of arbitrary length is not regular.


Lets look more into the pumping lemma for regular languages. The informal wording from wikipedia is:

Informally, it says that all sufficiently long words in a regular language may be pumped — that is, have a middle section of the word repeated an arbitrary number of times — to produce a new word that also lies within the same language.

So, lets take the language "a followed by some number of b followed by an a" which can be written as ab*a. Within this regular language you have aa and aba and abba and abbba. Applying the pumping lemma to this I can take the bbb part and stick in it in there again and if it still matches, it is a regular language. So, putting bbb in the middle of abba I get abbbbba which is still part of the language (refiddle). You can do this for any thing that is a regular language.

On the other hand, if you can put this in there and have something that isn't part of the language be matched, or should be part of the language but isn't matched you have a proof by contradiction that the original language isn't regular.

So, lets say "I have a language of binary palindromes of arbitrary length" The regular expression to match it is ([01]?)([01]?)([01]?)([01]?)([01]?)[01]?\5\4\3\2\1 (note, I'm being a bit free with the language here being an extended one with back reference shorthand, but noting that would take a bit more text to properly represent it otherwise).

The above regular expression will match 010 and reject 011. It will match 10101 but not 10111. Great. But the pumping lemma says that I should be able to put an arbitrarily large amount of the middle into the middle. Now, the reader should go back and look at that regular expression... it has 5 back references. It can't "store" more than 5 in there. Thus, if I was to put

12345.....54321
101001111100101

in there, it wouldn't match this string (refiddle), but that is a palindrome. You can stick any palindrome of 12 or more characters in there and it will not match.

Thus, using the pumping lemma, I can say "palindromes of arbitrary length is not regular". If it was, I could stick a thousand or million 1s in the middle there and pump it up... but I can't, so it isn't.

(Those who have dealt with regular languages before will likely recognize the palindrome of [01] is the parentheses matching language with a slight twist... which also isn't regular - see also Can regular expressions be used to match nested patterns? or To make sure: Pumping lemma for infinite regular languages only?)

A key part of the regular language is that it represented by a finite number of states. What the contradiction with 101001111100101 did was to try to make it longer than the longest possible word that the language could recognize - which broke it.

Why not add more states? Well, you can only put a finite number of states in there. ([01]?)...([01]?)[01]?\100000...\1 ... and I'll make a palindrome that is 200,002 characters long, and it won't recognize it. If you need an infinite number of states to present the language, it isn't a regular language (it might be context free (and palindromes are), but that's something else).

  • You may not care to, but would it be possible to clarify what the pumping lemma is? I recently read about it in a French linguistics book, but couldn't really wrap my mind around the formal language. If that should be asked as a separate question in the context of programming languages/parsing I'd be happy to do so :) Not sure if the OP knows either, so it might be worth clarifying, maybe not! – Chris Cirefice Nov 13 '14 at 4:14
  • @ChrisCirefice asking to define a pumping lemma would be a poor question because it is easily answered with a link to an off-site resource. Have you had any college courses on this topic? I have had two (undergraduate and graduate), and both covered palindromes and other non-regular constructs, as well as how to prove a regular expression (the CS term, not programming) cannot detect arbitrary strings with those properties. – user22815 Nov 13 '14 at 4:29
  • @Snowman I figured, and no - I've only read about it in a linguistics textbook, but I have not yet taken any courses on it. I'm taking Compiler Design and Construction, but proving languages to not be regular wasn't part of the course work. I imagine it will be covered in Automata Theory, which I will be taking in a year. I guess I'll just google around a bit until I find a good resource on it. Thanks for the warning about the question! – Chris Cirefice Nov 13 '14 at 4:31
  • @ChrisCirefice in general, asking to define anything is a bad question. The good questions are after you understand part of something, maybe are writing a program to explore some aspect of it, and need specific help understanding something. Even then, check the "applies to graphic" to make sure you are asking in the right place. Further discussion on this topic is more appropriate for meta – user22815 Nov 13 '14 at 4:38
  • This was a really great read, thank you. – Regular Joe Nov 15 '14 at 1:19
5

No.

As others have mentioned, regular expressions cannot match palindromes of arbitrary length.

However, many programming languages have extended regular expressions in a way that puts them theoretically between regular and context-free languages, allowing them to match certain patterns that a strict regular expression by the textbook would not be able to match. Perl is one of these languages.

Java accepts several Perl extensions, but not the recursion tag required to implement this. What Perl can do is see that the first and last characters of the string match, then recursively use the same regex to attempt to match whatever is in the middle. Java does not support this nonstandard regex extension.

Here is another question that affirms it is not possible, and one more that offers a mathy CS proof of why it is not possible.

  • I am new to Perl, and while looking for my answer, I could only find answers in Perl. How to you say that Java accepts Perl extensions? I quite dont get your point – GermanShepherd Aug 22 '14 at 3:42
  • POSIX defines two types of regular expressions which pretty much any regex engine you are likely to encounter will support. Perl adds its own extensions which Java partially supports. – user22815 Aug 22 '14 at 3:54
  • The differences revolve around adding new character classes, ways of capturing text, recursion, etc. Perl regexes are easily the most powerful out there, but that power comes at a steep price in complexity and sometimes performance. Not all regex engines choose to implement the Perl way of doing things. Sometimes one little feature has a large cost. – user22815 Aug 22 '14 at 3:55
0

An answer from SO.

https://stackoverflow.com/questions/233243/how-to-check-that-a-string-is-a-palindrome-using-regular-expressions

I played around with these, and I had some success.

(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1

\W(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1\W

I think the real answer is that RE is a poor method for finding palindromes.

  • Palindromes of length N is a regular language. All possible palindromes is not a regular language. That will not match 1234567654321 as a palindrome. – user40980 Nov 13 '14 at 3:20
  • It is trivial to write a FSA to match a palindrome, but you need a PDA to match any palindrome. – user22815 Nov 13 '14 at 4:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.