Re: Theoretical CFG 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.