Today we introduce the non deterministic
finite automata. We're going to
use the subset construction to show that
every language that can be recognized by
any non deterministic finite optimata is
still a regular language, in that it can
be also be recognized deterministic finite
automata. We're, then, going to add
something to the non deterministic
automata called epsilon transitions that
allow, sort of spontaneous jumps from
state to state and we will, in fact, show
that these automata, even though
they look more powerful, also can
recognize only the, the regular languages.
A non deterministic automaton has the
ability to be in several states at once. A
transition in a non deterministic
automaton is from some state, say Q, on an
input of, say, A. It can go to...several
different states, so we can have several
transitions all labeled A. And this is the
thing that allows the automaton to, in a
sense, guess, to be non-deterministic. It
can go from state Q to, really any of
these states. And therefore, it actually
goes to all of those states at once. Okay.
Likely a DFA, a Non-Deterministic Finite
Automaton, or NFA as we we'll call it, has
one start state, where computation begins.
The NFA can have any number of final
states and an input is accepted of any
sequence of choices, leads from the start
state to some final state. The intuition
is that the NFA is allowed to guess which
way to go, but it is able to always guess
right since all the guesses are followed
in parallel and the NFA gets credit for
the right guesses no matter how many wrong
guesses it also makes. In our example of a
nondeterministic finite atomaton the
states are squares of a chess board. In
general, you can occupy several different
squares at a time. In a red move, which we
represent by the input symbol "r". You get
to move to any adjacent red square. So in
effect, you replicate yourself and move to
all of them. Similarly if the input is B
you can move to any adjacent black square,
so in effect you move to all the black
squares. The question we ask is whether
the given sequence of R and B inputs can
get you from the start state, which will
be the upper left corner, to the one final
state, which is the lower right hand
corner. The answer is yes. If any sequence
of choices we'll get, with each input,
leads us from the upper left to the lower
right. It is not necessarily that all such
choices do. And, in general, there will
always be some choices that lead us
astray. Okay. So here's our example. The
chess board will be rather tiny. It's only
three by three instead of eight by eight.
But the ideas are all the same. Okay, now,
using the, moves which, I have summarized,
in a, uh... a transition table, but which
follow the intuition that I, that I gave
you, we're going to examine the sequence
of inputs RBB. That is one red move
followed by two black moves. We'll start
in the start state, state one only. So, so
we're gonna show state one there. Now we
get an R input so we can move to any of
the red squares adjacent to square one or
in terms of the transition table, here's
the row for state one. We look under R and
we find states two and four are the
possible moves. Okay, notice that adjacent
really means one king move so that, from
state one, let's say you can get to two,
four, or five. Obviously, only two and
four on a red move, and only five on a
black move. Okay, so, after reading the R,
we go from states one, state one, to states
two and four. Okay, so now we are in
states two and four and b comes in so what
do we do? Well from state two, we can go
to one, three, or five. You can figure
that out either by noticing that one,
three, and five are the adjacent, black
squares. Or you can just look it up on the
table here, here in row two, the black,
moves are, are, are one, three, and five.
Now how about state four? Well, from four
you can go to, to one, five or seven on a
black move. Some of those states are
already listed. But, the point is that
between two and four the state should be
up to a one, three, five and seven. Now,
that's all for the... the first B. Now the
second B comes in. And, from one you can
only go to five. From three, same thing.
You can only to five. On a, on a black
move. Now from five you can go to a lot of
states. You can go to one, three, seven, and
nine. And from seven you then only go to
five. After reading the BB, sorry, RBB,
you are in, in fact, all the odd numbered
states or actually all the black, the black
squares Since, nine is, is the, accepting
state, we say that RBB is accepted by this
automaton. The fact that it's also in
states five, one, three, and seven, are
not relevant to the question of whether
it's accepted or not. Here the components
of an NFA, they look exactly the same as
for the DFA and will typically use the
same letters to represent them. The big
difference is in the type of the
transition function and we will see that
on the next slide. For the NFA delta of
state two and input A is now a set of
states, possibly empty rather than a
single state as it was for the DFA. The
extension of delta to strings is a bit
more complex. The basis is still easy.
Delta of Q and the empty string is just
the set containing Q, since the only state
you can reach on no input is the state you
are in. For the induction, suppose we
start in state Q, and we read string W
followed by symbol A. We first compute
delta(q, w), the set of states you get from
Q by following W. So let's, from Q, let's
say following paths, labeled W, we might
get to states P1, P2, and so on. Okay,
then, for each of these states, say, P1
and P2 and so on, we're going to use the
given delta function, to find the set of
states they each get to on A. So let's
say P1 might go to these two states, I
don't know their names. P2 might also go
to that one, and several others, and so
on. You find all the states you can get
to, but always on transition labeled A.
And, the resulting union, this set, is
delta of Q and WA. Okay. The language of,
of nondeterministic automaton is simply
the set of strings that it accepts, that is,
the set of strings W, such that when you
compute delta of Q, Q naught and W,
that Q naught is of course the start state,
when you compute delta of Q naught and W you
have a set that contains at least one
final state. Okay, the language of the,
non deterministic automaton that we
designed to represent moves on a
chessboard is actually quite tricky to
describe. For strings consisting only of
Bs, it's easy. You start in, the, only in
the state one. And on the next move, with
B, you only go to state five. So you're
only in the set containing five. Another
B. If you'll notice will take you from
five to 1-3-7-9, so now after the second B
you're in 1-3-7 and nine only. The next B,
well. Each of 1-3-7-9 only go to, only
have b as an adjacent black square. 
Their other adjacent squares are red.
So after 1-3-7-9 you are now
in just the set of 5. And from 5 you
go to 1-3-7-9, and so on. As a result, you
accept all the even length non-empty
strings. That is BB, BBBB,
six B's, eight B's, and so on. And you
don't accept strings B. Or BBB,
and, and so on. The odd length strings.
It's less clear what happens when there
are R's in the input. Obviously an
acceptance stream must end in B because
only state 9 is accepting and you only
get there in a B move. But I'll leave it
to you to figure out exactly what strings
with one or more R's are accepted. Okay.
In a sense, a DFA is an NFA that just
doesn't have any non-determinism. Formally
given a DFA with a transition function
which we'll call delta sub D you can
create and NFA with the same states and
inputs as the DFA, and the same start and
final states. The only thing different
about the NFA is that the form of its
transition function is what it has to be
for an NFA. It gives you a set of states,
rather than a single state. But that set
of states in Delta N, will be exactly. The
one state that delta D gives you for a
given, Q and, and input A. As a result,
the NFA, after reading some sequence of
inputs, is in the set of states that's
always a singleton. It always contains only
the one state that the DFA is in. Okay.
So that says any language accepted by DFA
can be accepted by some NFA and in fact
the NFA really looks the same as the DFA,
and, and it almost is the DFA. Okay
surprisingly, for any NFA, there's a DFA
that accepts exactly the same language.
And the proof is called the subset
construction. And, and this construction
was the thing that, as a graduate student
convinced me that there was something to
computer science theory. It had only been
discovered five years before, and it
boggled my mind to see a construction
that, while it could be described easily,
resulted in something that could not be
grasped. The problem...is that the
number of states of the DFA that you get
from a NFA can be a, have a... the number can
be exponential in the number of NFA
states. Now if the NFA has three states,
the DFA can have eight states. That's not
a big deal. I can visualize an eight state
automaton. But if the NFA has ten states,
the DFA could have a thousand states, and
that's already becoming quite hard to
imagine. And if the NFA has twenty states,
which is still something we can visualize,
the DFA can have a million states, and
we're completely lost, even though we know
the DFA exists. Oh. And by the way, the
situation is not, nearly as bad in prac,
in, in practice as it looks in theory.
Many of the non deterministic automata
that you construct in things like
compiler design, when you convert them to
DFA the number of states is not, doesn't
really grow much at all, if at all. In
fact the chess NFA we just introduced
actually has an equivalent DFA with fewer
states as we shall soon see. So, let's
start with a typical NFA. It has the
conventional names for the components,
although we'll use delta N for its
transition function to distinguish it from
delta D, which will be the, transition,
function for the, equivalent DFA that
we're going to construct. Now, in the,
DFA, states are... represented by two to the
Q, which is... Two to the Q is a
mathematical notation for the power set of
Q , that is the set of all subsets of Q.
'Kay. Notice that if a set Q has N
elements, then it, its power set has two
of the N elements, so the notation sort of
makes sense, okay. So the important point
to remember is that the DFA states are
actually sets of states of the NFA. And
there can be an exponential number of them
compared with the number of states in the
and, the inputs of the DFA are the same as
the inputs of the NFA. That's the set
sigma. The start state of the DFA is the
set containing the start state of the NFA.
Remember that the states of the
deterministic automaton are sets of states
in the non-deterministic automaton. Thus
the start state, which is a single state
of the DFA, is written as a set of states in
the NFA. Of course, the set contains only
the start state of the NFA. Okay, then the
final states of the DFA are all those
states that, uh, they're thought of as sets
of states in the NFA, contain a member of
F. Remember F is the set of the final
states for the NFA. Just to make sure we
understand what's going on, the DFA states
have names that looks like sets of states.
However, they are single objects. Okay, an
analogy that might, be useful to make is
with a class of object in a language like
Java or C++, whose values happen to be set
of objects from some other class. Okay,
the transition function, delta D is
defined by, delta D applied to, now, and
this is not a set of, this is a set of NFA
states, but it's a, this is a single state
of the DFA. And input A. Is the union over
all, well all the states Q.1 through Q.K.
Of. What you get when you take the delta N
as the transition function of the non
deterministic automaton, and apply it to
that QI and, A. So you have P is Q1, P is
Q2. And, you see where you get to 1A.
[sound] And like that. And so on. And this
set of NFA states is the name of the DFA
state that you get to when you go from
this state of the DFA on input A. To the
next state of the DFA. Okay. We're going
to as an example of the subset
construction do a lazy construction of DFA
sta tes. That's generally much better than
assuming we need all the subsets of NFA
states. Okay, we gotta start Of course we
know we need the set containing the
initial states. We surely need as one of
the DFA states, the set containing one,
cause that's, that's the initial state of
the NFA. But we're only going to create
rows for states when we, when we are sure
that we need them. Okay, so, obviously, we
need the starred state of the, DFA, which
is the set containing one. So we'll begin
the construction with a row for the set
containing, the set containing one. Now,
from the NFA table, which I've outlined
here in red. We know that on R, one goes
to 2-4, and, and on B, it goes to five.
And since this set is a singleton, that's
all we need to know. So we know
immediately that, in the DFA, the set
containing one goes to the set containing
2-4 on R, and set containing five on B.
Now, I've put, these two sets, made rows
for them in the table. I haven't filled
out the rows, yet. But we know that we're
gonna have to, because they obviously are
states that you can reach from the starred
state of the DFA. Okay, here, we've filled
out the row for the DFA state whose name
is the set containing 2-4. Okay. Well on
input R, we'd look at the, uh, and again
this is the NFA table, we look at the
things marked in red. That is, on two, so
from two on input R you go to four and
six, and from state four, on input R, you go
to two and eight, so from the set containing
2,4 on R you go to 2,4,6,8 and this is a
single state of the DFA. And, since I
haven't encountered the state before, I
now create a row for it. Reminding me that
I'm gonna have to figure out what its
transitions are, sometime in the future.
Let's see, and from state 24 on input B,
you just look at, where the NFA goes on
those two states, and you take the union
of 1-3-5 and 1-5-7, that's 1-3-5-7. And that's in
there, and I also put it here, cause I'm
gonna have to figure out its row in a
minute. Now we fill out the row for 5.
And that's fairly easy. You just look at
the row for 5 on the NFA table. And
you enter the, the states right there. 
2-4-6-8, we've seen already. So we
don't have to create a row for it. 
1-3-7-9 has not been created. So
we will create it now. And I've always
started because notice, that is the a, a
final state of the DFA. It has the final
state of the NFA state 9. Okay, now for
2-4-6-8. Again, I've in the
NFA table, I've put in red, the relevant
rows. For R, I just take the union. I've
got 4-6, 2-8, 2-8, 4-6. So the union is
2-4-6-8. That's a state I've seen already,
not interesting. On B, I've got 1-3-5,
I've got 1-5-7. Got 3-5-9, 5-7-9. The union
of that is 1-3-5-7-9. Got a new state, so
I add it to the list of rows that I need
to construct. And by the way it's also a
final state, because it contains 9.
Okay. Here's the row for 1-3-5-7. Again,
same process. You again get 2-4-6-8, on R.
And you get 1-3-5-7-9, on B., and these are
both states you've seen, so we add no new
rows, for 3-7-9. Oh, we just compute it's
entries. Perhaps the only interesting
thing is that on a B, all of 1, 3,
7 and 9 go to only, only 5 on B
so what you get is a set containing
only 5. That is a state that we've seen
before, as, of course is 2-4-6-8.
So we don't have to add any new
states, and, finally, 1-3-5-7-9
also yields no new states, and,
so, we now have completed. The entire
transition table for the DFA. Notice it
only has seven states, while the NFA
had nine. So it actually shrunk the number
of states. Again, you have to be rather
lucky to do that, but it does happen.
We're going to prove that the NFA and the
DFA reconstruct, but the subset
construction are equivalent. That is they
define the same language. You must thus
show that if one accepts a string W if and
only if the other does. That is the two
languages are each contained in the other
and therefore they are the same. Now
notice that delta N is a set of NFA states
Delta D on the other hand is a single
state, but its name is a set of NFA
states. So it is quite reasonable, at
least or it's a, a, an interesting pun to
argue that this as a set, as a single
state, is the same as that, as a set of
states. For the basis, let W be the empty
string. Then, delta N of Q zero, and empty
string is the set containing Q zero, by
the basis rule for extending the delta for
non deterministic automata. And delta D
of the set containing Q zero and the empty
string is the set containing Q zero again
by these extended delta rule for
deterministic automata. For the
inductive step, we'll assume the inductive
hypothesis that the states of the DFA,
that the DFA and the NFA get to on stream
W are the same sets for all streams
shorter than W. And we'll prove the
statement for W itself. Okay, W is of
length at least one, so we can write it as
string X followed by symbol A. And we can
assume the inductive hypothesis holds for
X, because it is clearly shorter than W.
That is, we're going to assume that delta
N of Q zero and X is delta D of set
containing Q zero and X. And we'll call
that set S. Let T be the set of states the
NFA can get to by starting in state S, and
following a transition on A. So that is,
we have. >> Let us say, there's a set S of
states and coming out of various of these
states are transitions on A. >> Okay, by
the rules of the extended delta for NFA's
the set T of all the states that you get
to. Is delta N. Of Q. Zero and W. By the
subset construction. We also know the
delta D of S and A, is T. Thus, delta N of
Q zero and W, and delta D of Q zero and
W are both T. The latter of course is
by the, the extension rule for, for
deterministic automa... Deterministic
automata. That is how you compute the
extended delta. So we have therefore
proved the inductive step. Okay, we are
now going to an additional ability to
NFAs. The ability to make a spontaneous
transition on epsilon. That is, without
using any input. We just saw that the NFA,
while it can be a convenience in designing
automata, still accepts only regular
languages. The same is true for the new
model, which we'll call epsilon NFAs. But
they can be a real convenience in
constructing automata. And yet they still
accept only the regular languages. Here's
an example of an epsilon NFA. The
transition diagram has some arcs labeled
epsilon, and we can follow any such arc
without adding to the sequence of inputs
that the automaton has processed. That is,
epsilon is invisible as far as input
strings are concerned. We also see the
transition table for this automaton.
Notice it has a separate column for
epsilon. But epsilon is not an input
symbol, it's not a member of the input
alphabet. For example, from the start state
A, let's look at A, there is only one
transition on zero to E, and that's why,
you have a set containing E over here.
There's only one transition that's to B
on input 1. So that's why you have a set
containing B there, and there are no
transitions out on, on the empty string.
So we have, the empty set symbol, is,
represents the transitions from A on, in,
on, on epsilons, it's not an input. It's,
it represents spontaneous, transitions.
Let's look at, E now. On zero, there's a
transition to F, and only to F. So you get
the set containing F. There... There are no
transitions at all from E on a 1, so
you get the empty set. And on epsilon you
have transitions to both B And C, so
that you have the set containing BC. At that
 entry. Okay. Notice that if we were
in state E, and the input is 1, then we
can spontaneously go to B on epsilon. And
then, on the 1, wind up in C. Okay. We
can also go spontaneously from E to C on
epsilon, and wind up on D in input 1.
Okay. Now to do the conversion of epsilon
NFAs to regular or ordinary NFAs we need
to have the notion of the closure. The
closure of a state Q, which we're going to
write to CL of Q, is the set of states we
can get to starting in Q and following
only epsilon transitions. So for example,
from A you can get nowhere else on
epsilon, right? If you're here there are
no epsilon transitions out. As a result.
The closure of A is just the set
containing A. Of course, you can, you're
in A to begin with, so you can stay in A.
So closure of this state always contains
at least itself. Closure of E is trickier.
Okay, we start in E, surely we can reach
E. Then there are epsilon transitions from E
to B and C. So, we can, surely get to B
and C. But now we have to see where we can
get to from B and C. Well, C doesn't have any
epsilon transitions out, so we can't get
any, anywhere else, but B also has a
transition on epsilon to D. D has nowhere
else to go on epsilon. So, the conclusion
is that the conclos.. the closure of e
on, is, All of B, C, D, and E. Okay, and
that's what we've written here. Then we
also are going to need to apply the
closure operator to sets of states and,
the definition is quite simple. The
closure of the set of states is just the
union of the closures of each of those
states. Now. We need to describe the
operation of a, an epsilon NFA by
defining the extended delta. And again,
it's intended to tell us about where we
can get from a given state, following a
path labeled by a certain string W.
However epsilon, the empty string, is
invisible along paths. So, W only involves
the real input symbols of the automaton.
And as a result, we follow paths that are
labeled by real symbols of W, but with
arcs labeled epsilon interspersed
as much as we like. So. For the epsilon
NFA, delta had of QA, is not the same as
delta of Q and A, because delta of Q and A
does not include any epsilon transitions.
So we're gonna keep the hats on the
extended delta when we need them. Okay. So
for the basis, delta had Q with epsilon is
the closure of the state Q, so it's not
just Q if you can reach anywhere from Q on
epsilon then that's included in the
closure and therefore in the delta hat.
For the induction, suppose the input is
string X followed by symbol A. Start by
figuring out what delta had of Q, O, and X
is. Say it is a set of states S. Okay, for
example let's suppose that X is BC. And we
might start from Q zero, and we'll follow
paths labeled epsilon, and then a B. And
then maybe more epsilon, possibly
none. To state what we follow a, a C, and
then maybe more epsilons. Suppose this
takes us to a set of states S. To compute
delta hat of Q and X followed by A, we
look at all the states in S. We find all
the A transitions, no epsilons now. We
then have to take the closure of these
states, that is, we follow all the epsilon
paths. [sound]. And finally get to the
state that is, that is, this side, this
set of states is the, is delta hat of Q
and XA. Here's an, here is an example.
This is the automaton that we've been
playing with. And say delta hat of A in
epsilon is the closure of A. That's, the
basis rule. And that's just set containing
A, because A doesn't get your anywhere on
epsilon. Now, I'd say the delta hat of A
and zero is the closure of E, which is, B,
C, D, and E as we discussed earlier. Why
closure of E? Because when we already
determined that the closure of A is A,
and, on zero. The only place you can get
to from A on a zero, on, on a zero is E,
so we have to close E. Now, delta hat of
A. And the string zero one. I claim is
closure of C and D, which is actually is
just C and D. Why is it closure of CD?
Well look. We already know that delta hat
of A and zero is the set containing B, C,
D, and E. Okay. So we're, so here, here,
here and here. Now on a one, where can I
go from any of those states. Well from E
no place, from D no pace, from B to C and
from C to D. So the only place that you
can get to from B C D and E on a one are C
and D. So that's why we start with C and
D. We take the closure now neither C nor D
have any epsilon transition out. So we
conclude that Delta hat of A and 01 is the set
containing C,D. What that means is, if you
look at. Starting at A, all the paths
labeled 01, with as many epsilons as you
wish thrown in the middle those paths lead
you only to C and D. That is, there's this.. 
There's this...and there is this.
Okay. And that's it. Okay. Finally, the
language of an epsilon NFA is defined in the
expected way. For any string W, you
compute the extended delta of the starred
state, and that's string W. And if you
see, you see if any of the resulting set
of states is a final state, except W, if
so, and if not, then not. We now want to
show that the NFA and epsilon NFA models
yield the same languages. The regular
languages of course. One direction is easy
since an ordinary NFA is an epsilon NFA
which that happens to have no transitions
on epsilon. But proving that for every
epsilon NFA, there's an ordinary NFA that
accepts the same language we're going to
have to get rid of the epsilon
transitions, we do that by combining them
with the next transition on a real
input. If you're following the text you
should notice that this construction is
somewhat different from the one in the
text, but both constructions work. Here
we'll have to change the set of final
states while the one in the book doesn't,
but this construction is I believe, a bit
simpler. This is a picture of how we are
iron out the epsilon transitions. We
start from the state, here, and we follow
all the epsilons we can using the closure
operator. And I'm sorta imagining that the
yellow area represents paths that are
labeled only by epsilons. We then follow
all the transitions from any of the states
we reach on a real input symbol A. The
ordinary NFA is able to get to on input A
any of the states that can be reached
using these transitions of the epsilon NFA
on input A, that is, the ordinary NFA will
have a transition from here to each of
these states on input A. Now, since we
don't close the states after transition on
A, we have to make additional final
states. Those that can reach a final state
on epsilons only. So, for example, if this
state might not be final, but it might be
able to reach by epsilons, some final
state. If so, that there is the final
state of the epsilon NFA, but in the,
the ordinary NFA we're constructing, we're
gonna make this state be final because
in effect, it has the power
of the final state in the epsilon NFA.
Whenever you get there, epsilons will
take you to the final state. So you
know that whatever got you here, will be
accepted by the epsilon nfa. So you
want the ordinary NFA to accept it
as well. We're gonna start with an epsilon
NFA that has the usual components, Q for
states, sigma for inputs and so on. But
we'll use, delta E for its transition
function. Okay, and we're gonna construct
an ordinary NFA with the same set of
states, the same input symbols, same start
state. A different set of final states,
perhaps, F prime, and its transition
function will be called delta N. Okay.
Now, the way we compute delta N of Q and A
is as follows. We want to start at state
Q. We're going to close Q. That is by
following epsilon paths, to get to some
set of states S. Okay. Delta N. Of Q. And
A. Take all the states in S. We find all
their transitions on A. And. This, this is
the set of states that is delta sub N of
Q and A. That is in the ordinary automaton,
Q, gets you, on A., anywhere that
the epsilon NFA can get you by following
zero or more epsilons and then an A. Okay.
Now, F prime, the set of final states of the
ordinary NFA, is the set of states Q such
that the closure of Q contains the state
of F. That's the thing that, again that
allows you, if there is a epsilon path to
a final state, then this state gets the,
the same accepting power. That wasn't
needed in the epsilon NFA. Okay, we're
not going to prove this, but the idea is
that the NFA on any input W enters the set
of states of the epsilon NFA enters on the
same input, using epsilons transitions
anywhere it likes except at the end after
reading all the real inputs of W. However,
state P in delta N of Q zero and W is a final
state, if, in the epsilon NFA, B can get to
a final state following all the epsilons.
Okay, thus the fact that the equation
holds that is this, this equation here. Is
enough to say that W is accepted by either
both or neither of the automata. That is if
delta E contains an accepting state, then
delta N of Q... of Q zero and W, will
contain a state, which has also been made
accepting, because it can reach on
epsilons an accepting state of the
epsilon NFA. Here's the epsilon NFA we
used before as an example and the NFA,
ordinary NFA that we construct. The
interesting changes are marked in red So,
first of all here are the non-, all of the
non-trivial closures. That is the closure
of well, the closure of B. Because B goes
to D on epsilon, the closure of B is B and D.
And the closure of E, which we
worked out before is, well... E goes to B
and C. B goes to D, so E can go to B,
C, D, and E. Okay, in the NFA without
epsilon transitions, we need to change the
transition from E on input one. And, the
reason is that we first take the closure
of E, which of course is B, C, D, and E.
And then we ask, where can I get to from
those states on a one? And, if you look at
the, the epsilon NFA from B, C, D, and E,
all you can get to are C and D. Okay, so
we put C and D, it becomes the entry there
where as in the epsilon NFA it was the
empty set. Kay, the transition from E on,
on zero actually doesn't change. The
reason is that, that B, C and D have no
transitions on, on zero. So, the fact that
we can get to them on epsilon doesn't
help us when the input is, is, is a zero.
Okay, finally, since the closures of B and
E include the final state D, they become
final states as, as well as D, in the
ordinary NFA. And that's the entire
construction. So, we now have three
different formalisms for describing
languages. The DFA, the NFA, and the
epsilon NFA. They look progressively more
powerful, and in fact, they are more
powerful in the sense of the things they
can do. But, in fact, they give us exactly
the same class of regular languages. Very
soon we're gonna see a fourth formalism
called regular expressions that look quite
different from these. But in fact, also
gives us exactly the regular languages. So
we might be getting the idea that the
regular languages are quite a natural
class of languages, and indeed they are.
We should notice that the added power of
NFAs and epsilon NFAs are quite useful.
For example we shall talk about designing
automata to recognize sets of key words,
say the reserved words in C or some
other programming language. That is an
important task for building a compiler for
the language. We could design a DFA for
the task, but it is much easier to start
with simply DFAs for each keyword and
stretch the chain of states... Say, for "else" it's
just an E, an L, an S, and an E, and of course
that's a final state. That's how you
recognize your keyword "else." Then, we'll
connect them all with epsilon transitions
from a single start state. So, you'll put
an epsilon here, this becomes the start
state. And you'll have epsilon transitions
to a lot of these chains, for all the
keywords, and they of course all end 
in a final state. And that's all there is to it.
You've got an, you've got an epsilon  NFA. 
And then we're gonna convert them
to a deterministic automaton, cause the
deterministic automaton is necessary
for if you want to actually execute an, an
automaton. That is only a DFA can be
implemented. No one, yet, has yet invented
a non deterministic computer, although I've heard
that Intel is working on it.