lorentz@ms.secs.csun.edu (Richard J. Lorentz) (05/18/91)
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 |