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}


I wrote:
|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?


Well, I didn't miss just something, I missed it completely. The
_complement_ of the language is not a CFL. But this language is, as
someone else already pointed out in another reply. My apologies for the
confusion ...


kind regards,


Jos aka jos@and.nl
--

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