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

Greg Bacon <[email protected]> writes:

> In message <87ekdzmute.fsf-898kb7mjOftiFBjP29LO3Ww0nxwv98vyZkel5v8DVj8@public.gmane.org>,
>     Daniel Martin writes:
> : 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.
>
> 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.

I stand by my original statement ("any FSM can be reversed...") but
I'll admit that the sketchy proof outline ("Just draw ...") is missing
a step.  Instead, it should say:

  Just draw the FSM as a bunch of circles and arrows, reverse the
  direction of each arrow, and switch the "start" and "accept" states.

Then, in your example you end up with a NFA that accepts strings which
end in "1".  

(Yes, switching the start and accept states may result in multiple
start states - if your definition of NFAs doesn't allow for that, then
you need to introduce an additional state to act as start that
transitions to everything the start states transition to.  It's easier
to get a more expansive definition of NFA.)