A nondeterministic machine is just like a deterministic machine except that its transition behaviour isn't deterministic. If you know the state a deterministic machine ℳ is in then you know what state it will go to when you give it character a (or b or whatever). With a nondeterministic machine you only know the set of states that it might go to next. Notice that a deterministic machine is simply a nondeterministic machine where this set-of-states-that-it-might-go-to is always a singleton.
Nondeterministic machines (hereafter NFAs - "nondeterministic finite automata") are a conceptual nightmare. The fact that they are nondeterministic makes for a crucial difference between them and deterministic machines. In the deterministic case you don't have to distinguish in your mind between its behaviour in principle and its behaviour in practice, since its behaviour in practice is perfectly reproducible. That means that you can think of a deterministic machine either as an abstract machine - a drawing perhaps - or as a physical machine, according to taste. With NFAs there is a much stronger temptation to think of them as actual physical devices whose behaviour is uncertain, rather than as abstract objects. And the difficulty then is that NFAs are not physically realisable in the way one would like.
So if NFAs are so nasty, why do we study them? The answer is that they
tie up some loose ends and enable us to give a smooth theoretical treatment
that improves our understanding and appreciation. So let us get straight what
they are for. We started this course with a connection between machines and
languages. A machine accepts strings and recognises a language. A (physical)
nondeterministic machine can accept strings in exactly the same way that a
(physical) deterministic one does. You power it up, and feed in the characters
one-by-one and when it's finished reading the string its either in an accepting
state or it isn't. The subtlety is that a nondeterministic machine, on having read
a string, might be in any of several states, perhaps some of which are accepting
and perhaps some not. The only sensible definition we can give of an (abstract)
nondeterministic machine recognising a language is this:
The language recognised by a nondeterministic machine ℳ
is the set of strings that one of its physical realisations might
accept.
The task of remembering and understanding this definition is made much easier for you once you notice that the definition for recognition of languages by deterministic machines is simply a special case of this.
Nondeterministic machines are useful to us because of the combination of two facts.
(i) If L is a language recognised by a nondeterministic machine ℳ then there is a deterministic machine ℳ which can be obtained in a systematic way from ℳ that also recognises L.
(ii) There are circumstances in which it is very easy to produce a nondeterministic machine that recognises a language but no obvious easy way to produce a deterministic one.
Let us now prove (i) and illustrate (ii).
(i) Suppose I have a nondeterministic machine ℳ, presented to me in its start state. I have a handful of characters {c1 , c2 , c3 . . .} that I feed to the machine one by one. Initially I know the machine is in the start state. But after I've given it c1 I know only that it is in one of the states that it can go to from the start state on being given c1. And after I've given it c2 I know only that it is one of those states it can reach from the start state in two hops if given c1 followed by c2 and so on. We seem to be losing information all the time. But all is not lost. Although I do not have certain knowledge of the state ℳ is in, I do nevertheless have certain knowledge of the set of states that it might be in. And this is something I can keep track of, in the following sense. I can say "If it's in one of the states s or s' or s'' and I give it character c then either it was in s in which case it's now in s''' or s'''' or it was in s' in which case it's now in . . . . In other words
Now comes the trick. Think of the set-of-states-that-it-might-be-in as a state of a new machine! One way of seeing this is to think of the states of the new deterministic machine as the states of uncertainty you might be in about the state of the nondeterministic machine. We have seen something like this before: in the discussion of the thought-experiment we were viewing states of the machine as states of knowledge of the string-so-far; this time we are thinking of states of the new (deterministic) machine as states-of-knowledge-of-what-state- the-nondeterministic-machine-might-be-in.
If we take seriously the empty set of states in the power set construction for states then we can make sense of the convention that missing arrows take you to a fail state.
I mentioned earlier that the concatenation of two regular languages is regular. Suppose I have a deterministic machine ℳ1 that recognises L and a deterministic machine ℳ2 that recognises K. The idea is to somehow "stick ℳ2 on the end of ℳ1".
The difficulty is that if w is a string in LK, it might be in LK for more than one reason, since it might be decomposible into a string-from-K followed by a string-from-L in more than one way. So one can't design a machine for recognising LK by saying "I'll look for a string in K and then - when I find one - swap to looking for a string in L". You have to start off imagining that you are in ℳ1; that much is true. However when you reach an accepting state you have to choose between (i) staying in ℳ1 and (ii) making an instantaneous hop through a trap-door to the start-state of ℳ2. That is where the nondeterminism comes in. These instantaneous hops are called "ε-transitions". You do them between the clock ticks at which you receive new characters. I don't like ε-transitions and I prefer theoretical treatments that don't use them. However, they do appear in the literature and you may wish to read up about them.
For those who do like ε-transitions, here is a description of a nondeterministic machine that recognises LK. It looks like the disjoint union ℳ1 ⨆ ℳ2 of ℳ1 and ℳ2. Transitions between the states of ℳ1 are as in ℳ1 and transitions between the states of ℳ2 are as in ℳ2 . In addition for each accepting state of ℳ1 there is a ε-transition to the start state of ℳ2.
For those of you who - like me - do not like ε-transitions, here is a different nondeterministic machine that recognises LK. Like the last one, it looks like the disjoint union ℳ1 ⨆ ℳ2 of ℳ1 and ℳ2. Transitions between the states of ℳ1 are as in ℳ1 and transitions between the states of ℳ2 are as in ℳ2. In addition, whenever s is a state of ℳ1 and c a character such that δ(s, c) is an accepting state of ℳ1 , we put in an extra arrow from s to the start state of ℳ2 , and label this new arrow with a 'c' too. The effect of this is that when you are in s and you receive a c, you have to guess whether to stay in ℳ1 (by going to an accepting state in ℳ1 ) or make the career move of deciding that the future of the string lies with K, in which case you move to the start state of ℳ2.
The manner in which we got rid of ε-transitions in this case is perfectly general. You can always get rid of them by introducing a bit of nondeterminism in the way we have just done. (And you can go in the other direction too.)
Next: 5 A Coursework