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

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: