home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compiler / 1886 < prev    next >
Encoding:
Text File  |  1992-11-16  |  1.2 KB  |  36 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!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: Compilers Central
  7. Date: Sun, 15 Nov 1992 14:57:29 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-11-077@comp.compilers>
  10. References: <92-11-067@comp.compilers>
  11. Keywords: parse, question
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 21
  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. |[ ... ] Does anyone have any ideas about this problem?
  22.  
  23. If you apply the pumping lemma, it would show that this language is _not_
  24. a context free language, so there exists no CFG that can generate this
  25. language. No word in this language can be written
  26.                       i  i
  27. as UVWXY, such that UV WX Y, for i >= 0 is an element of this language too.
  28. Or am I missing something here?
  29.  
  30. kind regards,
  31.  
  32. Jos aka jos@and.nl
  33. -- 
  34. Send compilers articles to compilers@iecc.cambridge.ma.us or
  35. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  36.