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.