home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1876 < prev    next >
Encoding:
Internet Message Format  |  1992-09-07  |  2.0 KB
  1. Path: sparky!uunet!mcsun!Germany.EU.net!tools!tl
  2. From: tl@tools.de (Thomas Lewerenz)
  3. Newsgroups: comp.theory
  4. Subject: Re: cute problem regarding finite automata
  5. Date: 05 Sep 92 14:43:52 GMT
  6. Organization: TooLs GmbH, Bonn, Germany
  7. Lines: 35
  8. Distribution: inet
  9. Message-ID: <TL.92Sep5154353@fred.tools.de>
  10. References: <40853@gremlin.nrtc.northrop.com>
  11. NNTP-Posting-Host: fred.tools.de
  12. In-reply-to: johnson@nrtc.northrop.com's message of 4 Sep 92 18:04:00 GMT
  13.  
  14. In article <40853@gremlin.nrtc.northrop.com> johnson@nrtc.northrop.com (Greg Johnson) writes:
  15. >   Here is a cute problem, perhaps suitable as an exam question.
  16. >   I offer it to all beleaguered professors trying to think up comp
  17. >   questions!  ;-)
  18. >
  19. >   Define a rotation of a string A as follows:  divide A into substrings A1 and
  20. >   A2 such that A1 A2 equals A; A2 A1 is a rotation of A.
  21. >
  22. >   For the string `abcd', the rotations are abcd, dabc, cdab, bcda.
  23. >
  24. >   Now let L be a regular language, and let Rotate(L) be the language consisting
  25. >   of all rotations of strings from L.  Is Rotate(L) regular?  Give proof
  26. >   or counter-example.
  27. >
  28. >   - Greg Johnson
  29. >     johnson@nrtc.northrop.com
  30.  
  31. I'm not beleaguered nor am I a professor, but here it is:
  32.  
  33. Let L be a regular language and M be a deterministic finite automaton
  34. accepting L. Let M' be a nondeterministic finite automaton with
  35. eps-moves which behaves as follows:
  36. On input x M' first guesses nondeterministically any of the states of M, say A,
  37. and memorizes it in its finite control. Then it simulates M on input x starting
  38. at state A. Whenever the simulation reaches one of the final states of M, M'
  39. chooses nondeterministically to go on or make an eps-move to the starting state
  40. of M. M' accepts x iff it reaches A on the end of input and has made exactly one
  41. eps-move from a final to the starting state of M during the simulation.
  42. (A more formal description of M' is left to some clever examinee ;-))
  43. Clearly M' accepts x iff x \in Rotate(L) and therefore Rotate(L) is
  44. regular. 
  45.     q.e.d.
  46.  
  47. --
  48. Thomas Lewerenz, tl@fred.tools.de
  49.