Related articles 

Theoretical CFG question norlin@essex.ecn.uoknor.edu (19921113) 
Re: Theoretical CFG question jos@and.nl (19921115) 
Re: Theoretical CFG question pab@cs.arizona.edu (19921116) 
Re: Theoretical CFG question jos@and.nl (19921117) 
Newsgroups:  comp.compilers 
From:  jos@and.nl (Jos Horsmeier) 
Organization:  Compilers Central 
Date:  Sun, 15 Nov 1992 14:57:29 GMT 
References:  9211067 
Keywords:  parse, question 
norlin@essex.ecn.uoknor.edu (Norman Lin) writes:
For i>=1, let b(i) denote the string in 1(0+1) that is the
binary representation of i. Construct a CFG generating
 +
 {0,1,#}  {b(1)#b(2)# ... #b(n)  n>=1}

[ ... ] Does anyone have any ideas about this problem?
If you apply the pumping lemma, it would show that this language is _not_
a context free language, so there exists no CFG that can generate this
language. No word in this language can be written
i i
as UVWXY, such that UV WX Y, for i >= 0 is an element of this language too.
Or am I missing something here?
kind regards,
Jos aka jos@and.nl

Return to the
comp.compilers page.
Search the
comp.compilers archives again.