At 10:49 PM +0100 12/8/00, Viktor Rosenfeld wrote:
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:[EMAIL PROTECTED]
HertzSCHLAG: http://www.informatik.hu-berlin.de/~rosenfel/hs/
--
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
unsuscribe me!
_________________________________________________________
James K. Kroger, Ph.D.
Center for the Study of Brain, Mind, and Behavior
Department of Psychology
3-N-4D Green Hall
Princeton University
Princeton, NJ 08544-1010, USA
Tel: (609) 258-1291
Fax: (609) 258-1113
[EMAIL PROTECTED]
http://www.princeton.edu/~kroger/home/
