home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compiler / 1899 < prev    next >
Encoding:
Text File  |  1992-11-17  |  1.5 KB  |  40 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!darwin.sura.net!europa.asd.contel.com!emory!sol.ctr.columbia.edu!eff!world!iecc!compilers-sender
  3. From: jos@and.nl (Jos Horsmeier)
  4. Subject: Re: Theoretical CFG question
  5. Reply-To: jos@and.nl (Jos Horsmeier)
  6. Organization: AND Software BV Rotterdam
  7. Date: Tue, 17 Nov 1992 12:31:04 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-11-091@comp.compilers>
  10. References: <92-11-067@comp.compilers> <92-11-077@comp.compilers>
  11. Keywords: parse
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 25
  14.  
  15. norlin@essex.ecn.uoknor.edu (Norman Lin) writes:
  16. |For i>=1, let b(i) denote the string in  1(0+1)   that is the
  17. |binary representation of i.  Construct a CFG generating
  18. |          +
  19. |   {0,1,#}    -   {b(1)#b(2)# ... #b(n) | n>=1}
  20.  
  21. I wrote:
  22. |If you apply the pumping lemma, it would show that this language is _not_
  23. |a context free language, so there exists no CFG that can generate this
  24. |language. No word in this language can be written
  25. |                      i  i
  26. |as UVWXY, such that UV WX Y, for i >= 0 is an element of this language too.
  27. |Or am I missing something here?
  28.  
  29. Well, I didn't miss just something, I missed it completely. The
  30. _complement_ of the language is not a CFL. But this language is, as
  31. someone else already pointed out in another reply. My apologies for the
  32. confusion ...
  33.  
  34. kind regards,
  35.  
  36. Jos aka jos@and.nl
  37. -- 
  38. Send compilers articles to compilers@iecc.cambridge.ma.us or
  39. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  40.