Re: OT: regular expression question

[Hubert Chan <hackerhue@crosswinds.net>]

>>>>> "Viktor" == Viktor Rosenfeld <rosenfel@informatik.hu-berlin.de> writes:

    Viktor> 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...

    Viktor> I don't think so.  L = {xx^r} is surely context free, but not

Actually, the language would be L = {xx^r}U{xAx^r} where the A means any letter
in the language.  (Remember - aba is a palindrome too.)

    Viktor> regular.  I think, the PDA that recognizes this language is fairly
    Viktor> easy to construct, but it's late, and I've done enough theoretical
    Viktor> computer science for today.

For simplicity, assume that our alphabet is {a,b}.  Then the CFG is

S: aSa | bSb | a | b

Simple, eh?

Then converting it to a PDA is trivial (or it would be if I remembered how to
do it. ;-) )

Hubert

-- 
____     |     -----------------------------------------------------------
|  /   --+--
| /   ___|___    Hubert Chan <hackerhue@crosswinds.net>
| \   | _|_ |
|__|  |__|__|    GCS/M d- s:- a-- C++ UL+(++++) P++ L++ E++ W++ N++ o?
|        |       K? w--- O++ M- V- PS-- PE+++ Y+ PGP+ t+ 5 X R- tv+ b+
|      / | \     DI++++ D G e++ h! !r !y
|     /  |  \
|        |     <><------------------ http://www.crosswinds.net/~hackerhue/

PGP/GnuPG fingerprint: 6CC5 822D 2E55 494C 81DD  6F2C 6518 54DF 71FD A37F
Key can be found at http://www.crosswinds.net/~hackerhue/hackerhue.asc