({0,1,2,3}, {a,b,c}, {(0,a,0), (0,b,0), (0,c,0), (0,a,1), (0,λ,2), (1,b,0), (1,c,0), (2,a,2), (2,b,2), (2,c,2), (2,b,3), (3,a,2), (3,c,2)}, 0, {2,3})
Design a machine that accepts strings over {a,b,c} of the form: a string containing an even number of a's followed by a string that starts with b and ends with c. Note: This example is not so compelling. Need something better!.So, for example, the string cabcacbac should be accepted by your machine, becase cabcacbac breaks it up into a piece with an even number of a's followed by a piece that starts with b and ends with c.
One easy way to do this is to construct two machines, one
for "even number of a's" and one for "starts with
b and ends with c", and hook them together
with an λ-transistion. Specifically, the
λ-transistion takes us from the accepting state of
the first machine to the start state of the second machine.
That way, you'll leave the first machine knowing you've read
a string containing an even number of a's, and
start the second machine knowing you can only end up in an
accepting state if you subsequently read something that
starts with b and ends in c.
This is, of course, too easy! So let's try to make a machine that accepts strings that look like some number of strings accepted by the above machine, all tacked end to end. In other words, I should accept a string if it can be broken up into pieces, each of which starts and ends with the same letter and has length at least 2
Hopefully you're starting to see that these λ-transitions make creating new machines from old ones quite easy. In fact we could have done both of our big examples just using regular old non-dterminism --- i.e. two or more transitions for the same state/character combination. However, the λ-transisions let us do things without having to pick apart the original machines and see how they work. That'll help us later when we construct algorithms on nondeterministic machines.
Definition: a nondeterministic finite automaton is an ordered 5-tuple (Q,Σ,Δ,s,W) where
This allows us to look at all the same kind of examples we had for deterministic machines, going back and forth from diagram representation to 5-tuple representation.
5-tuple definition | ({q0,q1,q2}, {a,b,c}, {(q0,b,q1),(q1,a,q1),(q1,b,q1), (q1,c,q1),(q1,c,q2)}, q0, {q0,q2}) |
diagram definition |
What about the rules governing how an NDFA computes? Well, we can borrow the idea of configuration, "yields in one step" and "yields in many steps" from DFAs, as long as we add the possibility of λ-transitions to "yields". However, "yields" kind of mean different things for DFAs versus NDFAs. Instead of (p,u) ⇒ (q,v) meaning "if you're in configuration (p,u) then after one step you will be in configuration (q,v)", for NDFAs we may only say that (q,v) is one possibility ... there may well be others.
For NDFA M = (Q,Σ,Δ,s,W), we say that configuration (p,v) yields in one step configuration (q,w) if x ∈ Σ ∪ {λ} we have v = xw and (p,x,q) ∈ Δ. This is sometimes denoted (p,v) ⇒ (q,w), or (p,v) ⇒M (q,w) when you need to clearly indicate which machine you're referring to.
(p,v) = (q1,w1) ⇒ (q2,w2) ⇒ ... ⇒ (qk,wk) = (q,w)
This is sometimes denoted (p,v) ⇒* (q,w) or, when you need to clearly indicate which machine you're referring to, (p,v) ⇒*M (q,w).Now the big question is how do we define "accept" and "reject" for NDFAs? Well, we define it the same way as for DFAs, it just means something a little different.
NDFA M = (Q,Σ,Δ,s,W) accepts string w if (s,w) ⇒* (q,λ) for some q ∈ W.
We can't talk about "the state we're in after all the input has been read", because there may be many possible states to be in after all the input is read, or the may be no possible states to be in with all the input read. This uncertainty is captured by the new yields definition, which says that (s,w) ⇒* (q,λ) if there is some sequence of configurations ....