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

On Wed, Mar 30, 2005 at 09:36:10AM -0500, Daniel Martin wrote:
> 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.)

Rather, the additional state should transition to all the original
accept states on the empty string.  (In general, NFA's may have such
transitions, though they can be algorithmically removed.)