Xref: utzoo sci.math:17551 comp.theory:2007
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!usc!nic.csu.net!csun.edu!ms.secs.csun.edu!lorentz
From: lorentz@ms.secs.csun.edu (Richard J. Lorentz)
Newsgroups: sci.math,comp.theory
Subject: Undecidable problems about CFL's.
Message-ID: <1991May17.211050.3096@csun.edu>
Date: 17 May 91 21:10:50 GMT
Sender: usenet@csun.edu
Reply-To: lorentz@ms.secs.csun.edu ()
Organization: School of Engineering and Computer Science, CSU Northridge
Lines: 11

While trying to think up questions for a final exam on Computability
Theory I got to thinking:  just when is the question  L=L'? decidable
for arbitrary CFL L and fixed L'.  For example, if L' = (0+1)* the question
is undecidable, but it L' is any finite set the problem certainly is
decidable.  But what if L'=0*1* ?  Is the question decidable now?  What
properties must L' have to make the problem decidable or undecidable?

Any insights, references, etc. would be appreciated.  By the way, I
decided to bag the whole idea of asking a question like this on the exam!
--
|   Richard J. Lorentz   |   lorentz@ms.secs.csun.edu   |   (818) 885-2733   |