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

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.