Xref: utzoo comp.theory:1663 sci.math:15867
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!usc!nic.csu.net!csun!news
From: bam@csunb.csun.edu (brad williams)
Newsgroups: comp.theory,sci.math
Subject: Re: A few questions on automata and languages
Message-ID: <1991Mar18.214618.2310@csun.edu>
Date: 18 Mar 91 21:46:18 GMT
Sender: news@csun.edu (News Administrator)
Organization: csun
Lines: 28


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