Re: OT: regular expression question
Peter Jay Salzman wrote:
> i know how to search for palindromes, for instance, a 3 letter palindrome:
>
> \(.\)\(.\)\(.\)\3\2\1
>
> recently, i started wondering if there was a way, using regex only, to
> express a palindrome of arbitrary letter length?
>
> i've used some grey matter, and the answer seems to be no, but there's nice
> symmetry here. maybe i'm missing something...
I don't think so. L = {xx^r} is surely context free, but not regular.
I think, the PDA that recognizes this language is fairly easy to
construct, but it's late, and I've done enough theoretical computer
science for today.
MfG Viktor
--
Viktor Rosenfeld
E-Mail: mailto:rosenfel@informatik.hu-berlin.de
HertzSCHLAG: http://www.informatik.hu-berlin.de/~rosenfel/hs/
Reply to: