# Optional: Non-Deterministic FSMs Optional: Non-Deterministic FSMs – This is an optional topic on theory of computation. We’re going to talk about deterministic and non-deterministic finite state machines. So there are many types of automata and we’re gonna talk about a few of them in the video about the Chomsky hierarchy. We started with one of the simplest types of automata, a finite state machine. This is an abstraction that has states, transitions in between states, and inputs that trigger transitions between states.

This is a relatively simple structure and many of the transitions that we’ve been seeing so far are deterministic, like the one on the left here. We have an automaton with two states 0 & 1. If you’re standing at 0 and you get to input a, there’s only one thing that can happen next, you need to go from 0 to 1. So the input a triggers only one transition. Because the input a completely determines where you want to go, this is called a deterministic transition.

A non-deterministic transition is one where the input doesn’t completely determine where you’re going to go. On the automaton on the right if you’re standing at state 0 and then you get the input a, there’s two things that can happen: you can go from 0 to 1 or from 0 to 2. Because the input doesn’t completely determine where you’re going, we call this a non-deterministic transition. In fact an non – one characteristic of non-deterministic finite state machines is that there can be a state where if you get an input there are more than two transitions that use that input.

There’s another way in which finite state machines can be non-deterministic and this is through epsilon transitions or empty transitions. Here we have an automaton that goes from 0 to 1 and this jump from 0 to 1 happens when you absorb nothing, so it’s like it’s like a spontaneous jump, and you’re probably thinking that that’s kind of a silly jump, why would we have that? Epsilon transitions are very useful because they allow you to cheat, they allow you to look ahead and in effect stand in two – on two states at the same time.

So here we have a finite state transducer for two words, city and cities, when you get city, it just returns the same word and when you provide cities as an input, it’s going to return the morphemes of the word, it’s going to return city-pl for the plural. And notice what happens when you’re standing on state 6. When you’re standing there you have the input cit and you’ve produced the output cit and then you start – you go from six and start sort of peeking over at what you have next and i – in the input and then you wait, in 8 at the input and then you wait, and then finally in nine you get the input s, and you know oh yeah this was the word cities and you can paste the output of the transition from nine to ten into what you had before.

So in effect if you were standing on state six, you were sort of waiting to see if the word was actually gonna be cities and in doing so you were peeking at what was gonna happen next until you got there. Epsilon transitions are very useful in this way. Those were non-deterministic behaviors. A deterministic finite state machine is one that doesn’t have these characteristics. For example when you are on – on a state and you get an input, there’s only one transition that can use that input. In the finite state machine we have here, if you’re in state zero and you get a c, there’s only one path out, the path from 0 to 1. Also in this finite state machine each transition reads the symbol.

The c, the a, the t. Cat. There’s no transition that reads epsilons. Here we have an example of a non-deterministic finite state machine. It’s non deterministic because it has empty transitions, epsilon transitions. If you go from zero to one two three four, you get cat epsilon which is the – produces the singular of the word. Likewise for dog, zero six seven eight nine, dog epsilon.

Any non-deterministic finite state machine can be transformed into a deterministic one. This is the same finite state machine but without the epsilons. So to get the word cat, you now go from zero one two three, and have that as the end state through which you exit for the singular. And if you want the plural you go one more step from three to four. This example is of a finite state machine that is non-deterministic because there’s more than one transition out of p that has the number one, so if you’re standing at the state p and you get the input one, two things can happen: it you can go from p to q, or you can cycle back into p.

So getting the input one does not completely determine what’s going to happen next. As I mentioned a little while ago, any non-deterministic finite state machine can be converted into a deterministic one. So here this FSM is non-deterministic because if you are in the initial state and you get a b, two things can happen: you can go into the end state, or you can cycle back where you were. This can be converted into this deterministic structure which has more states and more transitions but they both generate the same strings, they both generate the same language.

So why would we even have two of them? They’re – they generate the same languages and – but they have slightly different properties. For example, non-deterministic finite state machines or non-deterministic finite automata are easier to make. Frankly, they’re easier and they – there’s ways to convert them into deterministic finite state machines.

They also have fewer states so you can make more compact finite state machines if they are non deterministic. As we saw in the example before, the non deterministic one had two states and the deterministic one had three states, so that’s why we want non deterministic ones. But why do we want deterministic ones? Because there’s several problems in theoretical computation that are easier to solve for the deterministic versions.

There’s several ways to solve these that are easier and faster. Problems like minimization, trying to find out if the automaton that you have is the smallest possible automaton for the language you want to generate. The problem of equivalence: if you have two automata, are they generating the same language? If you have inc – the problem of inclusion for example if you have automaton A and it generates a language, and you have automaton B generating some other language, is this language a sub language of this other one? So is this language from automaton A a part of the language of automaton B? This is the problem of inclusion.

Finally the problem of universality. If you have an alphabet of possible inputs, does your automaton generate all of the possible strings out of the all – out of the possible inputs? So solving these problems is easier on deterministic finite state machines, which is why we want to have both of them. In summary there’s many types of automata, and one type is the finite state machine, and there’s two types of those, the deterministic finite state machines where each symbol – where you have a state and you get an input and there’s only one transition out of that state using that symbol, and also where you have no empty transitions anywhere.

A non-deterministic finite state machine is one where if you are at a state and you get an input you can have more than one transition from the same state. Also a non-deterministic finite state machine is one that can take empty transitions. We’re going to look at more types of automata when we talk about the Chomsky hierarchy.