Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!sunybcs!rutgers!umn-d-ub!cs.umn.edu!martin
From: martin@cs.umn.edu (Johnny Martin)
Newsgroups: comp.theory
Subject: Re: Questions on BNF.
Message-ID: <1990Mar15.171634.15800@cs.umn.edu>
Date: 15 Mar 90 17:16:34 GMT
References: <9003081854.AA28577@Neon.Stanford.EDU> <426@fornax.UUCP> <1990Mar14.001730.20147@cs.umn.edu> <431@fornax.UUCP>
Organization: University of Minnesota, Minneapolis - CSCI Dept.
Lines: 47

In article <431@fornax.UUCP> mahajan@fornax.UUCP (Sanjeev Mahajan) writes:
>In article <1990Mar14.001730.20147@cs.umn.edu>, martin@cs.umn.edu (Johnny Martin) writes:
>> 
>> I am working on a similar problem, minimizing grammars for a given
>> language.  The problem is: you can't use Greibach's theorem for
>> classes of grammars, it only works for classes of languages.  So I
>> don't think approach is going to work.  What we really need is a
>> undecidability theorem for grammars.
>> 
>
>No, Greibach's theorem does work as stated (that is, if LL and LR languages
>are closed under quotient with one symbol). Infact on the same page
>as the theorem is proved in Hopcroft and Ullmann, it is proved
>(using the theorem) that if G is an arbitrary CFG, then it is undecidable
>if L(G) is regular.
>
>
>Sanjeev


Yes, you're right.  Thanks for pointing out my error.  Grammar .vs. language:
it doesn't matter.

Anyway, back to the original question:

>> 3. Given a BNF grammar for a language can one (automatically) determine
>>    whether it is (a) LL, (b) LR.

On p. 356 of Aho & Ullman's the theory of parsing, translation, and
compiling: vol 1, the following two questions are stated to be
undecidable, but no proof is given:

    a. given a grammar G, is G an LL grammar?
       i.e., does there exist some value of k for which G is LL(k)?
    b. if G is not LL(1) is ther an LL(1) grammar G',
       where L(G') = L(G)?
    However, there is an algorithm for determining if G is LL(k) for fixed k.

On pp.556-7 of Harrison's introduction to formal langauge theory,

    a. L is a DCFL iff L is LR(k) for some k>=0
    b. it is udecidable whether a CFG G is a DCFL or whether G is
       LR(k) for some k.
-- 
Johnny Martin, Dept. of Computer Science, University of Minnesota, Minneapolis
martin@umn-cs.cs.umn.edu
--