home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1901 < prev    next >
Encoding:
Text File  |  1992-09-09  |  1.2 KB  |  28 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!secapl!Cookie!frank
  3. From: frank@Cookie.secapl.com (Frank Adams)
  4. Subject: Re: cute problem regarding finite automata
  5. Message-ID: <1992Sep09.171425.59846@Cookie.secapl.com>
  6. Date: Wed, 09 Sep 1992 17:14:25 GMT
  7. References: <40853@gremlin.nrtc.northrop.com>
  8. Organization: Security APL, Inc.
  9. Lines: 17
  10.  
  11. In article <40853@gremlin.nrtc.northrop.com> johnson@nrtc.northrop.com writes:
  12. >Define a rotation of a string A as follows:  divide A into substrings A1 and
  13. >A2 such that A1 A2 equals A; A2 A1 is a rotation of A.
  14. >
  15. >Now let L be a regular language, and let Rotate(L) be the language consisting
  16. >of all rotations of strings from L.  Is Rotate(L) regular?  Give proof
  17. >or counter-example.
  18.  
  19. Yes.  Outline of the proof:
  20.  
  21. Each state of the new machine is a set of possible tuples; each tuple is an
  22. initial state (of the machine M for L), a current state, and a flag
  23. indicating whether end of string has been found.  The initial states are
  24. <S,S,no> for each state S of M.  The accepting states are those containing a
  25. tuple <S,T,no> where S is the initial state of M and T an accepting state,
  26. or a tuple <S, S, yes> for any state S of M.  I will not spell out the
  27. transformations, but they are straightforward.
  28.