home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / 2919 < prev    next >
Encoding:
Text File  |  1993-01-24  |  1.7 KB  |  37 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!cs.utexas.edu!usc!news.service.uci.edu!ucivax!ucla-cs!ucla-ma!sonia!aps
  3. From: aps@sonia.math.ucla.edu (Alexei Stolboushkin)
  4. Subject: Re: solution or information needed
  5. Message-ID: <1993Jan24.042945.6448@math.ucla.edu>
  6. Sender: news@math.ucla.edu
  7. Organization: UCLA Mathematics Department
  8. References: <1993Jan19.151627.21525@matrix.com> <1993Jan21.153028.7679@cs.yale.edu> <1993Jan22.214830.26496@math.ucla.edu>
  9. Distribution: usa
  10. Date: Sun, 24 Jan 93 04:29:45 GMT
  11. Lines: 24
  12.  
  13. In article <1993Jan22.214830.26496@math.ucla.edu> aps@sonia.math.ucla.edu (Alexei Stolboushkin) writes:
  14. >In article <1993Jan21.153028.7679@cs.yale.edu> fischer-michael@cs.yale.edu (Michael Fischer) writes:
  15. >
  16. >...
  17. >
  18. >>limitations of these devices.  To see why {ww | w E {0,1}*} is not
  19. >>regular, for example, you need to know about the pumping lemma for
  20. >>regular sets and other techniques for proving non-regularity.  To see
  21. >>why it is not accepted by a pushdown store machine, it is useful to
  22. >     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  23. >certainly it IS context-free, and therefore accepted by a PDA.
  24.  
  25. ooops, I thought it is ww' (' for reversion), sorry. Yes, you're right,
  26. for any CF language there is n such that every word in the language
  27. of length >n can be represented as xyzuv, with |yzu|<n, |yu|>0,
  28. and all words xy^k zu^k v are also in the language. So it seems
  29. enough to consider one word of the form:
  30.     0^m 1^m 0^m 1^m, for some m>n,
  31. and all four situations, when yzu consists of 1's only, of 0's only,
  32. of 1's, and 0's, and of 0's and 1's.
  33.  
  34. A much more interesting exercise (and an instructive one), is to
  35. give an example of a non-CF language satisfying the above pumping
  36. lemma.
  37.