home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / 2917 < prev    next >
Encoding:
Text File  |  1993-01-23  |  2.0 KB  |  47 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!batcomputer!cornell!uw-beaver!news.u.washington.edu!serval!moscow.uidaho.edu!jed.cs.uidaho.edu!foster
  3. From: foster@jed.cs.uidaho.edu ()
  4. Subject: Re: solution or information needed
  5. Nntp-Posting-Host: jed.cs.uidaho.edu
  6. References: <1993Jan19.151627.21525@matrix.com> <1993Jan21.153028.7679@cs.yale.edu>
  7. Sender: news@moscow.uidaho.edu
  8. Organization: University of Idaho CS Dept.
  9. Date: Fri, 22 Jan 1993 16:25:43 GMT
  10. Message-ID: <C19KAw.GG2@moscow.uidaho.edu>
  11. Distribution: usa
  12. Lines: 33
  13.  
  14. To see why "copy languages" are non-regular, learn a pumping lemma for CFLs, 
  15. as was just suggested.
  16.  
  17. I recently read an interesting explanation of why copy languages are non regular.
  18. Think about "dependencies" in a string, which are produced by the process of 
  19. derivation.  Rather than be formal, I'll give an example.  For palendromes, the
  20. dependencies are nested.  For example:
  21.  
  22.             a  b   b  a   a   a   b   b   a
  23.             |  |   |  |       |   |   |   |
  24.             |  |   |  +-------+   |   |   |
  25.             |  |   +--------------+   |   |
  26.             |  +----------------------+   |
  27.             +-----------------------------+
  28.                       
  29. This property holds for all context free languages.  However, consider the 
  30. dependencies for non CF languages.  For example, one from a copy language:
  31.  
  32.             a   b   b   a   a   b   b   a
  33.             |   |   |   |   |   |   |   |
  34.             |   |   |   +-------^---^---+
  35.             |   |   +-----------^---+    
  36.             |   +---------------+  
  37.             +---------------+
  38. The dependencies cross.  This is evidence that a more complicated process
  39. took place when they were generated, one where the productions had to "be aware"
  40. of other productions "in context".
  41.  
  42. I thought this was cute.  Incidentally, I read about it in "The Linguistics of DNA",
  43. Davide B. Searls, American Scientist, Vol 80, Nov-Dec 1992, pp 579--591.
  44. -- 
  45. James A. Foster                           foster@cs.uidaho.edu
  46. Universty of Idaho                        Dept. of Computer Science
  47.