Tue, 17 Nov 1992 12:31:04 GMT

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) |

Newsgroups: | comp.compilers |

From: | jos@and.nl (Jos Horsmeier) |

Organization: | AND Software BV Rotterdam |

Date: | Tue, 17 Nov 1992 12:31:04 GMT |

References: | 92-11-067 92-11-077 |

Keywords: | parse |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.