jeff@shuksan.UUCP (Jeff Jongeward) (03/19/91)
I am posting this for a friend, Prof. Richard Lorentz, who currently has no postnews access: Newsgroups: comp.theory,sci.math Subject: Re: A few questions on automata and languages Summary: PLEASE DON'T! Expires: References: <13911@hacgate.UUCP> Sender: Reply-To: lorentz@secs.csun.edu (Richard J. Lorentz) Followup-To: Distribution: Organization: School of Engineering and Computer Science, CSU Northridge Keywords: PDA CFL DPDA DCFL automata languages In article <13911@hacgate.UUCP> carmi@ipla01.hac.com (Aviram Carmi) writes: > >Hi, I recently came across some interesting problems and I would >appreciate any thoughts on them, or pointers to references. These interesting problems that he "came across" are from a takehome test I gave last week. Please, let him do his own test. I'll have a word with him in class tomorrow. )-: >1) We know that for PDA's (push down automata) we may define > acceptance by empty stack or by final-state and in either > case we will get exactly the CFL's (context free languages). > Is this true for DPDA's (deterministic PDA's)? > stack DPDA? > >2) For any PDA can we prove that the set of strings that can > appear on its stack is a regular set? > >3) We know that the concatenation of two DCFL is not nesseccrily > DCFL, but can the concatenation of two DCFL's that are not > regular end up being regular? > >Thanks, > >Avi >-- >Avi Carmi EMail: carmi@ipla01.hac.com Phone: (818) 702-3179 Again, thanks for letting him do his own work. -- Richard J. Lorentz | lorentz@mx.csun.edu | "is well known" = rumor has | (818) 885-2733 | it that someone once did it.