home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1871 next >
Encoding:
Internet Message Format  |  1992-09-07  |  978 b 
  1. Path: sparky!uunet!sun-barr!ames!elroy.jpl.nasa.gov!usc!isi.edu!gremlin!charming!johnson
  2. From: johnson@nrtc.northrop.com (Greg Johnson)
  3. Newsgroups: comp.theory
  4. Subject: cute problem regarding finite automata
  5. Message-ID: <40853@gremlin.nrtc.northrop.com>
  6. Date: 4 Sep 92 18:04:00 GMT
  7. Sender: news@gremlin.nrtc.northrop.com
  8. Reply-To: johnson@nrtc.northrop.com
  9. Organization: Northrop Research and Technology Center
  10. Lines: 15
  11.  
  12. Here is a cute problem, perhaps suitable as an exam question.
  13. I offer it to all beleaguered professors trying to think up comp
  14. questions!  ;-)
  15.  
  16. Define a rotation of a string A as follows:  divide A into substrings A1 and
  17. A2 such that A1 A2 equals A; A2 A1 is a rotation of A.
  18.  
  19. For the string `abcd', the rotations are abcd, dabc, cdab, bcda.
  20.  
  21. Now let L be a regular language, and let Rotate(L) be the language consisting
  22. of all rotations of strings from L.  Is Rotate(L) regular?  Give proof
  23. or counter-example.
  24.  
  25. - Greg Johnson
  26.   johnson@nrtc.northrop.com
  27.