[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: OT: regular expression question

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:rosenfel@informatik.hu-berlin.de
HertzSCHLAG:	http://www.informatik.hu-berlin.de/~rosenfel/hs/

To UNSUBSCRIBE, email to debian-user-request@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org

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

Reply to: