Re: OT: regular expression question
Hubert Chan wrote:
>
> 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. ;-) )
Sure enough!
M = ({q}, {a, b}, {S, a, b}, delta, q, S)
where delta (d):
d(q, epsilon, S) = {(q, aSa), (q, bSb), (q, a), (q, b)}
d(q, a, a) = {(q, epsilon)}
d(q, b, b) = {(q, epsilon)}
Okay, I admit that we've been doing that two weeks ago in computer
science. :)
MfG Viktor
PS: I just realize that ASCII is no good for math. Oh well.
--
Viktor Rosenfeld
E-Mail: mailto:rosenfel@informatik.hu-berlin.de
HertzSCHLAG: http://www.informatik.hu-berlin.de/~rosenfel/hs/
Reply to: