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

Ronald J Kimball <[email protected]> writes:

> That's not a counterexample.  The FSM doesn't meet the stated criteria, as
> the accepting state has two ways in for the input 1.

Greg Bacon included too much context when replying - he was objecting
to my first paragraph, not the second.  The "one way in for each
input" is necessary only if the reversed machine is going to be a
deterministic finite automaton (i.e. a FSM).  He was not contending
that reversing the arrows led to a defective FSM.  His objection was
that the NFA you got by reversing the arrows led to no string
accepted, and not to what I had stated.

And he's right, in that reversing the arrows alone is not enough - you
need to also reverse the accept and start states in the general case.