Re: [SPOILER] Perl 'Hard' Quiz of the Week #2005-03-22

On Tue, Mar 29, 2005 at 10:05:49AM -0600, Greg Bacon wrote:
> In message <87ekdzmute.fsf-898kb7mjOftiFBjP29LO3Ww0nxwv98vyZkel5v8DVj8@public.gmane.org>,
>     Daniel Martin writes:
> 
> : Greg Bacon <[email protected]> writes:
> : 
> : > Somehow I noticed that reversing the directions of the transitions
> : > seemed to accept the reversed language but lost the property of
> : > tracking remainders.
> : >
> : > Testing seems to show this to be a valid approach, and I wish I knew
> : > why.  I need to look through the Linz book to see if this is a property
> : > of regular languages.
> : 
> : It's relatively straightforward to see that any FSM can be reversed
> : into a non-deterministic finite state machine that will accept the
> : language {reverse(s) | s in original FSM's language}.  Just draw the
> : FSM as a bunch of circles and arrows and reverse the direction of each
> : arrow.
> : 
> : When, as in this case, the original FSM has the nice property that each
> : state has only one way in for each letter ("0" or "1" in this
> : problem), and only one accepting state, then the reversed machine is
> : in fact a deterministic FSM.
> 
> An easy counterexample to that is an accepter for binary strings that
> begin with 1 (drawn below as an NFA):
> 
>              1       <.
>     ---> () ---> (()) -' 0,1
> 
> Reversing the transition from the start state results in an NFA that
> rejects all inputs, not the reversed language.

You have to switch the start and accept-state (if w.l.o.g. there's exactly 
one start and one accept-state). Then you got:

             1     <.
      (()) <--- () -' 0,1

and it works. For the quiz-example, start and accept states are the
same.


Frank