On Tue, Mar 29, 2005 at 10:05:49AM -0600, Greg Bacon wrote:
> In message
> <87ekdzmute.fsf-898kb7mjOftiFBjP29LO3Ww0nxwv98vyZkel5v8DVj8@xxxxxxxxxxxxxxxx>,
> Daniel Martin writes:
>
> : Greg Bacon <gbacon-85RWSX2tBRuL3ccDcF8u4Q@xxxxxxxxxxxxxxxx> 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.
>
> 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.
Nope. The "only one way in" requirement has not been met.
Your second state (()) has two ways of being entered after
receipt of a 1 - from either state a 1 will take it there.
So, you can't reverse this. (In the reversed DFA, which way
do you go from this state when you get a 1? Unless you switch
to a NFSA you can't go to both states.)
--
|
