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

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.

Greg