We now consider a variation of the FSM that will make it much easier to design FSM’s. The notion
of non-determinism is a fundamental one that we will revisit many times in this class. You already are
familiar with non-determinism from month 5 (Algorithms) and the theory of NP-Complete problems.
Here we will be more formal and careful with the definition.
We will show that anything you can do with a non-deterministic FSM you can also do with a
deterministic FSM, implying that using non-determinism in the design of an FSM always accepts a
regular set.
A deterministic FSM has an arrow coming out of each state for each symbol in the alphabet. If an
arrow is missing, we assume that it actually goes to a dead state, that is a state with two self-looping
arrows (for 0 and 1). A non-deterministic machine may have any number of arrows coming out of
each states with 0 and 1 appearing on the transitions a arbitrary number of times.
How do we run a non-deterministic machine? We have potentially many choices of directions to move
after reading each symbol of the input. Well we don’t really run the machine, at least not in the sense
that we run a deterministic machine. However, there is a very formal and precise definition as to which
strings are accepted by a given non-deterministic FSM. If we can read the symbols of a string and find
some path that ends up in a final state then we accept that string. On the other hand, if every choice of
path ends up in a non-final state then we reject the string.
For example, we will consider (b), (k) and (l) above and show how non-determinism helps construct
the machines more easily.
There are more complicated regular sets that do not yield to a casual attempt at designing the FSM,
but yield readily to a non-deterministic FSM. You will see some hard ones in your psets. This should
remind you of how hard it is to solve problems like Towers of Hanoi without recursion, even though in
principle recursion is just a convenient tool that can always be simulated with stacks and iteration.
It is common to discuss variations of machines in order to determine which variations actually allow us
to accept sets that we could not accept before. Almost all variations of FSM’s do not add power.
These include 2-way FSM’s, non-deterministic FSM’s, alternating FSM’s, and FSM’s with lambda
productions.
We show constructively how to take a non-deterministic FSM and turn it into a deterministic FSM.
This lets us complete the proof that Regular sets are closed under reversal. Regular sets are closed
under many operations, some of which are hard to prove.
One interesting implication of this is that a binary string is divisible by three if and only if its reverse is
divisible by three. We can prove this by taking the FSM for the former machine, constructing its
reverse, and check that it is identical to the original. The only thing is, that it may accept the same set
and not be identical. In order to do this right, we have to minimize both machines and then they are
identical if and only if they accept the same set. This means we need to learn how to minimize FSM’s.
of non-determinism is a fundamental one that we will revisit many times in this class. You already are
familiar with non-determinism from month 5 (Algorithms) and the theory of NP-Complete problems.
Here we will be more formal and careful with the definition.
We will show that anything you can do with a non-deterministic FSM you can also do with a
deterministic FSM, implying that using non-determinism in the design of an FSM always accepts a
regular set.
A deterministic FSM has an arrow coming out of each state for each symbol in the alphabet. If an
arrow is missing, we assume that it actually goes to a dead state, that is a state with two self-looping
arrows (for 0 and 1). A non-deterministic machine may have any number of arrows coming out of
each states with 0 and 1 appearing on the transitions a arbitrary number of times.
How do we run a non-deterministic machine? We have potentially many choices of directions to move
after reading each symbol of the input. Well we don’t really run the machine, at least not in the sense
that we run a deterministic machine. However, there is a very formal and precise definition as to which
strings are accepted by a given non-deterministic FSM. If we can read the symbols of a string and find
some path that ends up in a final state then we accept that string. On the other hand, if every choice of
path ends up in a non-final state then we reject the string.
For example, we will consider (b), (k) and (l) above and show how non-determinism helps construct
the machines more easily.
There are more complicated regular sets that do not yield to a casual attempt at designing the FSM,
but yield readily to a non-deterministic FSM. You will see some hard ones in your psets. This should
remind you of how hard it is to solve problems like Towers of Hanoi without recursion, even though in
principle recursion is just a convenient tool that can always be simulated with stacks and iteration.
It is common to discuss variations of machines in order to determine which variations actually allow us
to accept sets that we could not accept before. Almost all variations of FSM’s do not add power.
These include 2-way FSM’s, non-deterministic FSM’s, alternating FSM’s, and FSM’s with lambda
productions.
We show constructively how to take a non-deterministic FSM and turn it into a deterministic FSM.
This lets us complete the proof that Regular sets are closed under reversal. Regular sets are closed
under many operations, some of which are hard to prove.
One interesting implication of this is that a binary string is divisible by three if and only if its reverse is
divisible by three. We can prove this by taking the FSM for the former machine, constructing its
reverse, and check that it is identical to the original. The only thing is, that it may accept the same set
and not be identical. In order to do this right, we have to minimize both machines and then they are
identical if and only if they accept the same set. This means we need to learn how to minimize FSM’s.
No comments:
Post a Comment