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 |greibach@maui.cs.ucla.edu (Dr Sheila Greibach) (05/28/91)
In article <1991May17.211050.3096@csun.edu> lorentz@ms.secs.csun.edu () writes: >just when is the question L=L'? decidable >for arbitrary CFL L and fixed L'. This is known, but I wouldn't dare use it for an exam even in a graduate course in cfl! The answer can be found (I think; I don't have it in front of me) in: Hunt & Rosenkrantz, "On equivalence and containment problems for formal languages" JACM (1977) Vol 24, 387-396 In a nutshell -- decidable if L' is bounded cfl (reduction to Presburger arithmetic); undecidable if L' is unbounded regular (in essence, reduction from the case L' = (0+1)* ). [A language L is called bounded if the are words w(1),...,w(n) such that L is included in w(1)* ... w(n)* ]