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

On Tue, Mar 29, 2005 at 10:05:49AM -0600, Greg Bacon wrote:

> : 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.

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.

Ronald