# Re: OT: regular expression question

>>>>> "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