Re: OT: regular expression question

[Hubert Chan <hackerhue@crosswinds.net>]

>>>>> "Hubert" == Hubert Chan <hackerhue@crosswinds.net> writes:

    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.

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

    Hubert> S: aSa | bSb | a | b

Oops.  There should be a "| \epsilon" at the end of that (where \epsilon is the
empty string) if you count the empty string as a palindrome.  If not, then you
should add "| aa | bb".

Hubert