Re: Theoretical CFG question

jos@and.nl (Jos Horsmeier)
Sun, 15 Nov 1992 14:57:29 GMT

          From comp.compilers

Related articles
Theoretical CFG question norlin@essex.ecn.uoknor.edu (1992-11-13)
Re: Theoretical CFG question jos@and.nl (1992-11-15)
Re: Theoretical CFG question pab@cs.arizona.edu (1992-11-16)
Re: Theoretical CFG question jos@and.nl (1992-11-17)
| List of all articles for this month |

Newsgroups: comp.compilers
From: jos@and.nl (Jos Horsmeier)
Organization: Compilers Central
Date: Sun, 15 Nov 1992 14:57:29 GMT
References: 92-11-067
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
--


Post a followup to this message

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