Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ucla-cs!maui.cs.ucla.edu!greibach
From: greibach@maui.cs.ucla.edu (Dr Sheila Greibach)
Newsgroups: comp.theory
Subject: Re: Undecidable problems about CFL's.
Message-ID: <1991May27.221353.3595@cs.ucla.edu>
Date: 27 May 91 22:13:53 GMT
References: <1991May17.211050.3096@csun.edu>
Sender: usenet@cs.ucla.edu (Mr. News Himself)
Organization: UCLA Computer Science Department
Lines: 19
Nntp-Posting-Host: maui.cs.ucla.edu

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)* ]