1
00:00:03,840 --> 00:00:08,290
Welcome back. In this video we're going to
talk about finite automata

2
00:00:08,290 --> 00:00:12,520
which we'll see in future videos are a
good implementation model for regular

3
00:00:12,520 --> 00:00:20,411
expressions. So in the last few videos,
we've been talking about regular

4
00:00:20,411 --> 00:00:24,217
expressions which we use as the
specification language for lexical

5
00:00:24,217 --> 00:00:28,875
analysis. And, in this video we're gonna
start something new. We're gonna talking

6
00:00:28,875 --> 00:00:34,003
about Finite Automata which are the For a
convenience as an implementation mechanism

7
00:00:34,003 --> 00:00:39,101
for regular expressions. And so regular
expressions and finite automaton are very

8
00:00:39,101 --> 00:00:44,325
close related. It turns out that they can
specify exactly the same languages called

9
00:00:44,325 --> 00:00:49,485
the regular languages. We won't prove that
in this course but we'll certainly make

10
00:00:49,485 --> 00:00:54,457
use of that fact. So, moving right along,
What is a finite automaton? Well, here is

11
00:00:54,457 --> 00:00:59,240
a typical definition as you might see in a
automaton theory textbook. Finite

12
00:00:59,240 --> 00:01:04,275
automaton consists of an input alphabet.
So, it's a set of characters that it can

13
00:01:04,275 --> 00:01:10,694
read. It has this finite set of states. We
should probably emphasize that. This is

14
00:01:10,694 --> 00:01:15,935
what makes it a finite automaton is that
it has some set of states that it can be

15
00:01:15,935 --> 00:01:20,921
in. One of those states is special and
it's designated as the start state. Some

16
00:01:20,921 --> 00:01:25,962
subset of the states are accepting states
so these are the states that. But, well,

17
00:01:25,962 --> 00:01:30,873
we'll just find that more in a minute but
intuitively, if the automaton terminates,

18
00:01:31,040 --> 00:01:35,114
after reading some input on one of these
takes that it accepts the input.

19
00:01:35,114 --> 00:01:39,188
Otherwise, it rejects the input and
finally the automaton has some set of

20
00:01:39,188 --> 00:01:43,765
state transitions that is in one state,
they can read some input and go to another

21
00:01:43,765 --> 00:01:48,598
state. So let's look at that little more
detail so a transition in a finite

22
00:01:48,598 --> 00:01:53,553
automaton. If I'm in, in this case I've
written out one particular transition

23
00:01:53,553 --> 00:01:58,703
here. We're in state one and we read the
input A then, the automaton can move to

24
00:01:58,703 --> 00:02:04,049
state two, okay. And there could be lots
of different transitions for the automaton

25
00:02:04,049 --> 00:02:09,525
from different states and different inputs
and its read the following way. If we're

26
00:02:09,525 --> 00:02:15,359
in state one on input A , we would go to
state two. And, if the automaton ends in

27
00:02:15,359 --> 00:02:20,286
an accepting state when it gets to the end
of the input that is going to do what's

28
00:02:20,286 --> 00:02:25,289
called accepting the string Meaning that
it will say yes, That string was in the

29
00:02:25,289 --> 00:02:30,646
language of this machine. So intuitively
the automaton starts in the start date and

30
00:02:30,646 --> 00:02:35,753
it repeatedly reads inputs one input
character at a time makes a transition. So

31
00:02:35,753 --> 00:02:40,798
it'll see what kind of transition it can
make out of its current state based on

32
00:02:40,798 --> 00:02:46,217
that input to another state and if that's
done ringing the input it's in one of the

33
00:02:46,217 --> 00:02:52,433
final states that it will accept.
Otherwise is going to reject the input.

34
00:02:52,433 --> 00:03:01,520
Now, one of the situations in which it
rejects, well, if it terminates In a state

35
00:03:02,620 --> 00:03:08,182
S, that's no one of the final or accepting
states, okay? So that ends in any other

36
00:03:08,182 --> 00:03:13,884
state besides one of the accepting states
and it's going to reject. If the machine

37
00:03:13,884 --> 00:03:20,984
gets stuck, Meaning it finds itself in a
state and there's no transition of that

38
00:03:20,984 --> 00:03:25,614
state on the input. So in particular,
let's say that in some state as a news and

39
00:03:25,614 --> 00:03:30,479
the input is A, and there's no transition.
There's no transition specified per state

40
00:03:30,479 --> 00:03:35,286
as an input A so the machine can't move
anywhere and it get stuck and that's also

41
00:03:35,286 --> 00:03:39,799
a rejecting state. And so in these two
situations, if, if you either get to the

42
00:03:39,799 --> 00:03:44,369
end of the input and it's not in a final
state or. If it never reaches the end of

43
00:03:44,369 --> 00:03:48,704
the input because it can stuck and both of
those cases it rejects the string. That

44
00:03:48,704 --> 00:03:55,665
string is not in the language of the
finite automaton. Now there's an

45
00:03:55,665 --> 00:04:00,252
alternative notation for Finite Automata
that I think is more intuitive for

46
00:04:00,252 --> 00:04:05,382
examples and so we're going to emphasize
that way of writing the mount. In this

47
00:04:05,382 --> 00:04:10,442
notation a state is represented as a known
graph which just draws a big circle. The

48
00:04:10,442 --> 00:04:16,662
start state is represented as a node that
has an edge or an arrow into it with no

49
00:04:16,662 --> 00:04:22,955
source. So, this is a transition into the
node but no source node that it comes from

50
00:04:22,955 --> 00:04:29,174
and that indicates the unique start state.
An accepting state is drawn as a node wit

51
00:04:29,174 --> 00:04:34,294
h just double circles like this. And
finally a transition is drawn as an edge

52
00:04:34,294 --> 00:04:39,427
between two nodes of the graph. So with
this as the time in this state that I'm

53
00:04:39,427 --> 00:04:44,690
circling in blue and I read the input a
well then I can move to this state at, at

54
00:04:44,690 --> 00:04:54,070
the tail of the arrow. So now, let's do a
simple example. Let's try to write up the

55
00:04:54,070 --> 00:04:59,440
automaton that accepts only the single
digit one. So all we need is start state.

56
00:05:00,340 --> 00:05:06,377
And will probably want an accepting state
as well and now the questions is what do

57
00:05:06,377 --> 00:05:12,123
we put in between the two? Well, there
would be some kind of transition here and

58
00:05:12,123 --> 00:05:18,160
it's a good guess that we should take that
transition if the machine reads the one.

59
00:05:18,160 --> 00:05:23,833
Now let me take a moment here to talk
about how the machine executes so let's

60
00:05:23,833 --> 00:05:29,579
label these states. Let's call this state
a and let's call this state b, okay. So

61
00:05:29,579 --> 00:05:35,154
the machine will have some input. Okay,
and we can write that input out will be

62
00:05:35,154 --> 00:05:39,630
here. So let's just say, we have the
single character one and it begins in some

63
00:05:39,630 --> 00:05:44,336
state namely the start state. And so, one
configuration of the machine is the state

64
00:05:44,336 --> 00:05:52,130
that it is in And the input. And typically
we would indicate where it is in the input

65
00:05:52,130 --> 00:05:57,335
by just a pointers saying what position it
is in the input. And, the important thing

66
00:05:57,335 --> 00:06:02,177
to know about input in [inaudible] the
input pointer always advances. So, when

67
00:06:02,177 --> 00:06:07,080
we, or it only advances so when we read a
character input, the input pointer moves

68
00:06:07,080 --> 00:06:11,881
to the right and it never moves back.
Alright, So from state a, we have a rule.

69
00:06:11,881 --> 00:06:17,333
We can see that we're in state a. The next
input character is a one and that allows

70
00:06:17,333 --> 00:06:22,719
us to take a transition to state b and so
now where b in state b and where as our

71
00:06:22,719 --> 00:06:28,105
input point well it's beyond the end of
the input indicating we are at the end of

72
00:06:28,105 --> 00:06:33,426
the input. And so now this is. We are in
an accepting state and we pass the end of

73
00:06:33,426 --> 00:06:42,048
the input and so we accept. Okay? So
let's, do another execution. So we start

74
00:06:42,048 --> 00:06:51,138
in state a and let's take as our input the
string zero. Okay. And I'd like to draw

75
00:06:51,138 --> 00:06:55,808
the pointer. Actually I should have drawn
it before the input so we'll al ways put

76
00:06:55,808 --> 00:07:00,708
the pointer between two input elements. In
this case it's a merely to the left of the

77
00:07:00,708 --> 00:07:05,368
one we're about to read. So in this case
we're about read zero so in state a. Our

78
00:07:05,368 --> 00:07:10,933
input is zero. We look at our machine. We
see that there is no transition on zero.

79
00:07:10,933 --> 00:07:16,637
All right? And so the machine stays stuck.
It doesn't make any move at all and this

80
00:07:16,637 --> 00:07:22,410
is our final configuration. And we could
see that we're not at the end of the input

81
00:07:22,410 --> 00:07:30,764
and so this is a reject. Okay, so in this
case the machine rejects that string as

82
00:07:30,764 --> 00:07:36,964
not being in the language of the machine.
Let's do one more example. Let's say that

83
00:07:36,964 --> 00:07:42,361
we're in state, well we're always
beginning in state a and the start state,

84
00:07:42,361 --> 00:07:48,342
and let's say our input this time is the
string ten, okay? And our input pointer is

85
00:07:48,342 --> 00:07:56,284
there. All right? So again we're in state
a. The input is a one and so we'll move to

86
00:07:56,284 --> 00:08:01,380
state b. And now the input doesn't change.
Just the input point changes but I'll just

87
00:08:01,380 --> 00:08:05,383
copy the input over to show the
difference. Now the input pointer has

88
00:08:05,383 --> 00:08:10,206
advanced cuz we've read one character of
input and now we're in another state. And

89
00:08:10,206 --> 00:08:15,838
now we can see that we're in state b. Our
next input is zero and there is no

90
00:08:15,838 --> 00:08:21,840
transition on zero from state b and so
even though we're in an accepting state, b

91
00:08:21,840 --> 00:08:27,842
as a final state, it's one of the accept
state and we haven't consumed the entire

92
00:08:27,842 --> 00:08:33,252
input. And so this, The machine also
rejects this string so this is also a

93
00:08:33,252 --> 00:08:43,662
reject. And in general we can talk about
the language. Of a finite automata that is

94
00:08:43,662 --> 00:08:56,401
equal to the set of...accepted strings.
Okay? So the language of a finite

95
00:08:56,401 --> 00:09:00,905
automaton, when I'm talking about the
language of a finite automaton, I mean the

96
00:09:00,905 --> 00:09:06,705
set of strings that the automaton accepts.
So now let's do a more complex example.

97
00:09:06,705 --> 00:09:12,449
Let's try to write out an automaton that
accepts any number of one followed by a

98
00:09:12,449 --> 00:09:18,616
single zero. So once again well need a
start state and we'll also need a final

99
00:09:18,616 --> 00:09:25,142
state and now let's start by thinking
about what's the shortest string is that's

100
00:09:25,142 --> 00:09:30,995
in the language of this machine. So in
this case, we know it has to end in a

101
00:09:30,995 --> 00:09:36,140
singl e zero. So a zero definitely has to
be, a zero transition has to be the last

102
00:09:36,140 --> 00:09:40,869
move and before that zero can come any
number of what? In a particular there

103
00:09:40,869 --> 00:09:46,095
could be no 1's. So one transition in this
machine is that from start state on input

104
00:09:46,095 --> 00:09:51,196
zero we can definitely go to the final
state because the single string consisting

105
00:09:51,196 --> 00:09:56,236
of a single zero isn't the language of
this machine. And now the only question is

106
00:09:56,236 --> 00:10:01,400
how do we encode the fact that any number
of 1's can proceed to zero? Well, there is

107
00:10:01,400 --> 00:10:06,907
an easy way to do that. We can just add a
[inaudible] by the start state. And take

108
00:10:06,907 --> 00:10:12,134
that transition if we read at one. And
what does this mean? This means that we'll

109
00:10:12,134 --> 00:10:17,295
stay in the state, state as longer are
we're reading 1's and as soon as we read

110
00:10:17,295 --> 00:10:22,260
zero, we'll move to the final state
because that has to be the end of the

111
00:10:22,260 --> 00:10:27,878
string if the machine is going to accept
it. So let's do a couple of examples to

112
00:10:27,878 --> 00:10:33,301
convince ourselves that this works. Let me
label this state?s again. So this is state

113
00:10:33,301 --> 00:10:42,212
a, and that's stat b. So Let's write out
here states and input. So we'll begin in

114
00:10:42,212 --> 00:10:50,569
state a and let's take as input 110, okay.
So let's do an accepting case first. All

115
00:10:50,569 --> 00:10:55,820
right, So our input pointer begins to the
left of the first character. So, we're in

116
00:10:55,820 --> 00:11:00,617
state a in start state. We're reading a
one and that says we should take a

117
00:11:00,617 --> 00:11:05,803
transition that puts us back in state a.
And so, we advance the input pointer. And

118
00:11:05,803 --> 00:11:10,924
now we consume the first one and, and
again we're in state a and the next input

119
00:11:10,924 --> 00:11:16,445
is a one so we'll make another transition
to state a. And the input cleaner will

120
00:11:16,445 --> 00:11:22,855
advance. So now we're in state a and the
next input is a zero and so we'll take the

121
00:11:22,855 --> 00:11:28,338
transition to b and now in this
configuration, so the input pointer has

122
00:11:28,338 --> 00:11:34,440
reached the end of the input we're in an
accepting state and so the machine

123
00:11:34,440 --> 00:11:41,113
accepts. 110 is in the language of this
machine. So now let's do an example where

124
00:11:41,113 --> 00:11:48,552
we will reject the input. And what
configuration do we begin in and again a

125
00:11:48,552 --> 00:11:54,116
configuration for a finite automaton that
just means you know a point in the

126
00:11:54,116 --> 00:11:59,825
execution it alwa ys consist of a state
and a position of the, the input pointer.

127
00:11:59,825 --> 00:12:05,317
So our initial state is a and now let's
just choose the string. I don't know,

128
00:12:05,317 --> 00:12:11,439
let's take 100 and let's confirm that this
is not in the language of the machine. All

129
00:12:11,439 --> 00:12:16,685
right, So we begin in state a and our
input pointer is there. Now we read a one

130
00:12:16,685 --> 00:12:21,999
and that means, well, you know. So it's
from state a transition of one. We stay in

131
00:12:21,999 --> 00:12:27,447
state a and the input pointer advances.
And now we see a zero. So from state a and

132
00:12:27,447 --> 00:12:33,747
input zero, we make a transition to state
b. And now the input point is here so now,

133
00:12:33,946 --> 00:12:39,652
we're in state b and we have an input of
zero but there is no transition the b and

134
00:12:39,652 --> 00:12:44,894
zero, there are no transitions out of b at
all and so the machine gets stuck, it

135
00:12:44,894 --> 00:12:50,003
can't get to the en of the input and
again, even though we're in an accepting

136
00:12:50,003 --> 00:12:55,842
state we haven't read the entire input yet
and so that means the machine will reject.

137
00:12:55,842 --> 00:13:03,322
And so, 100 is not in the language of this
machine. Up to this point a finite

138
00:13:03,322 --> 00:13:09,074
automaton consumes a character of input
every time it makes a move. So if you

139
00:13:09,074 --> 00:13:14,902
can't make any move at all, the input
pointer advances. Now we're talking about

140
00:13:14,902 --> 00:13:20,953
a new kind of move, the epsilon move and
the idea behind the epsilon move is that

141
00:13:20,953 --> 00:13:27,079
the machine can make a state transition
without consuming input, So for example if

142
00:13:27,079 --> 00:13:35,352
I have my states and I'm in state A and my
input. And let's just say that we have x1,

143
00:13:35,352 --> 00:13:41,799
x2, x3 and for some reason we're about to
read x2. When we make an Epsilon move the

144
00:13:41,799 --> 00:13:47,184
machine changes state but the input
pointer stays in exactly the same place.

145
00:13:47,184 --> 00:13:52,993
So the new configuration of the machine
that reinstate b, but our input pointer is

146
00:13:52,993 --> 00:13:58,590
still waiting to meet x2. So, you can
think of an epsilon move is a kind of free

147
00:13:58,590 --> 00:14:04,754
move from the machine it can, it can move
to a different state without consuming any

148
00:14:04,754 --> 00:14:09,759
input. And just to be clear here the
machine does not have to make the epsilon

149
00:14:09,759 --> 00:14:14,720
move. It's a choice so they can decide
whether to make the epsilon move or not.

150
00:14:18,280 --> 00:14:23,064
Now epsilon move, the first time we have
mentioned the possibility that a finite

151
00:14:23,064 --> 00:14:27,430
automata might have a choice and what
moves it makes. There's actually an

152
00:14:27,430 --> 00:14:32,274
important distinction between automata
that have choices and those have don't. So

153
00:14:32,274 --> 00:14:36,820
deterministic finite automata have two
properties, first of all, they have no

154
00:14:36,820 --> 00:14:42,030
epsilon moves so they must always consumed
input. And second, they only have one

155
00:14:42,030 --> 00:14:47,840
transition per input per state. What do I
mean by that? That means that if I look at

156
00:14:47,840 --> 00:14:53,510
any state in the deterministic automaton,
they can never have something like this

157
00:14:53,510 --> 00:14:59,390
where they have two possible moves for the
same input. All the outgoing edges in the

158
00:14:59,390 --> 00:15:04,858
deterministic automaton must have
different input labels. And then

159
00:15:04,858 --> 00:15:10,194
Nondeterministic Finite Automata are just
those not deterministic. So in particular

160
00:15:10,387 --> 00:15:15,465
a Nondeterministic Automata can have
epsilon moves so it can choose to move to

161
00:15:15,465 --> 00:15:20,737
another state without consuming input and
it could also have multiple transitions

162
00:15:20,737 --> 00:15:25,108
for one input in a given state so
something like this, is okay for a

163
00:15:25,108 --> 00:15:30,400
Nondeterministic Automata. Yeah. Let me
just point out really epsilon moves are

164
00:15:30,400 --> 00:15:35,479
enough to create a non-deterministic
automata and then at the second case where

165
00:15:35,479 --> 00:15:40,811
you have multiple transitions on the same
input can be simulated just by a slightly

166
00:15:40,811 --> 00:15:46,207
more complicated machine with epsilon move
so for example I can draw this machine in

167
00:15:46,207 --> 00:15:51,907
the following way. I can have or I can
simulate the machine that circled there in

168
00:15:51,907 --> 00:15:57,997
the following way. I can have a state with
two epsilon moves and then. Each of those

169
00:15:57,997 --> 00:16:04,348
states has a move on A so I were to label
the states one, two, and three. Then this

170
00:16:04,348 --> 00:16:09,612
would be the state that corresponds to
one. And this would be the state that

171
00:16:09,612 --> 00:16:14,144
corresponds to two and this state be, be
the state that corresponds to three. So

172
00:16:14,144 --> 00:16:18,733
anytime that we have multiple moves out of
the state on a single input we could

173
00:16:18,733 --> 00:16:23,552
always replace that by a few more states
with epsilon moves and have every state in

174
00:16:23,552 --> 00:16:28,198
the machine only have a single transition
for every possible input. So really the

175
00:16:28,198 --> 00:16:32,041
only fundamental difference between the
deterministic automata and

176
00:16:32,041 --> 00:16:38,082
non-deterministic automata is w hether
they have epsilon moves or not. A key

177
00:16:38,082 --> 00:16:43,929
property of a Deterministic Automata is
that it can only take one path through the

178
00:16:43,929 --> 00:16:49,414
state graph per input. So this is per
input. What do I mean by that? Well, the

179
00:16:49,414 --> 00:16:55,376
automaton always begins at the start state
and let's take a very simple input string

180
00:16:55,376 --> 00:17:00,776
like ABC and if we can look at the
sequence of states that the Deterministic

181
00:17:00,776 --> 00:17:06,204
Automaton will take, For that input, this
path through the state graph is completely

182
00:17:06,204 --> 00:17:11,108
determined by the input because again it
has no choice. In a given state, this can

183
00:17:11,108 --> 00:17:15,830
be one transition label day and this
continue to a state that it only has one

184
00:17:15,830 --> 00:17:20,734
transition labeled b and that goes to
another state that only has one transition

185
00:17:20,734 --> 00:17:25,577
labeled c. And so, every input determines
the path through the state graph of the

186
00:17:25,577 --> 00:17:30,178
automata will take. And, this is not true
for Nondeterministic Automata. So, it

187
00:17:30,178 --> 00:17:35,683
might be for example. That beginning in
the start state and on input a that there

188
00:17:35,683 --> 00:17:41,799
is some state I can go to on that input a
but there maybe another transition labeled

189
00:17:41,799 --> 00:17:47,310
a that would take me to a different state
so the automaton might be able to go to

190
00:17:47,310 --> 00:17:52,552
one of two different states and again
there might be also epsilon transitions.

191
00:17:52,552 --> 00:17:57,794
And so what happens with Nondeterministic
Automata is that in general as they

192
00:17:57,794 --> 00:18:03,305
proceed to the state graph is they execute
on the input, they could wind up in any

193
00:18:03,305 --> 00:18:10,303
number of different states. Okay. And the
rule with the non-deterministic automaton

194
00:18:10,303 --> 00:18:21,910
about when it accepts is that it accepts
if any path accepts. So if NFA Accepts, If

195
00:18:21,910 --> 00:18:36,753
some Choices Lead to an accepting state at
the end of the input. Now there's a

196
00:18:36,753 --> 00:18:41,460
[inaudible] automaton, I can choose what
move to make and as long as there are some

197
00:18:41,460 --> 00:18:46,110
choice it can make, then we'll get it to
an accepting state. So let's say switching

198
00:18:46,110 --> 00:18:50,532
colors here that you know this was an
accepting state down here and they took

199
00:18:50,532 --> 00:18:55,776
this path. Then it would accept and maybe
all of these other pass are rejecting

200
00:18:55,776 --> 00:19:00,206
pass, that doesn't matter. As long as
there is one path, a one set of choices

201
00:19:00,206 --> 00:19:04,814
the NFA could make to get it to an
accepting state at the end of the input,

202
00:19:04,814 --> 00:19:11,782
then we say that, that string is in the
language of the NFA. The fact that NFAs

203
00:19:11,782 --> 00:19:16,863
could get into multiple different states
depending on the choices they make during

204
00:19:16,863 --> 00:19:22,002
a run is important and will actually play
central role in the future video, so we're

205
00:19:22,002 --> 00:19:26,669
gonna do a quick example here to just make
sure that this is clear. So here's a

206
00:19:26,847 --> 00:19:31,455
little automaton and note that it is
Nondeterministic Automata from the start

207
00:19:31,455 --> 00:19:36,647
state there are two possible moves input
zero. And what we're going to do is just

208
00:19:36,647 --> 00:19:42,096
walk through in execution of this machine
on a sample input and see what different

209
00:19:42,096 --> 00:19:47,546
states it can get into. So we begin at the
start state and we should probably label

210
00:19:47,546 --> 00:19:52,717
our states actually so that we can refer
to them. Let's call them A, B, and C. And

211
00:19:52,717 --> 00:19:57,975
let's say at the first input is one and so
what does that mean? That means we'll take

212
00:19:57,975 --> 00:20:02,800
this transition. We'll just go from the
start state and come back to the start

213
00:20:02,800 --> 00:20:07,502
state and so the set of states that the
machine could be in after the first

214
00:20:07,502 --> 00:20:12,389
transition is just the set A. So it's
guaranteed to still be in the start state.

215
00:20:12,389 --> 00:20:17,276
So there's no, no choices with the first
move. Now let's say at the second input

216
00:20:17,276 --> 00:20:22,287
character is a zero and now we do have a
choice. We could either go to state B or

217
00:20:22,287 --> 00:20:26,773
we could go to state A. And, we could
think of this then as a set of

218
00:20:26,773 --> 00:20:32,552
possibilities that after we execute this
move, this transition, the machine could

219
00:20:32,552 --> 00:20:38,191
be in anyone of the set of states and
actually this completely characterizes the

220
00:20:38,191 --> 00:20:44,040
possibilities for the machine. We've only
read the second input character and now we

221
00:20:44,040 --> 00:20:49,680
could be in a set of states, okay? And we
could be either in state a or in state b.

222
00:20:49,680 --> 00:20:58,107
And so now let's say we read another zero.
And where could we go then, well if we're

223
00:20:58,107 --> 00:21:04,961
in state B we could make the transition to
state C but if we're in state A then we'll

224
00:21:04,961 --> 00:21:11,416
make the transition either to state B or
again to state A. So in fact we could be

225
00:21:11,416 --> 00:21:19,887
in anyone of the three states if we read
another zero. Okay? And now you, I think

226
00:21:19,887 --> 00:21:25,545
you can see w hat the rule is. So in every
step a Nondeterministic Automata is in a

227
00:21:25,545 --> 00:21:30,560
set of states of the machine and when it
reason, the input we consider all the

228
00:21:30,560 --> 00:21:36,025
possible moves it can make to compute the
complete set of states that could be in at

229
00:21:36,025 --> 00:21:40,387
the next step of the machine. Okay? And
then the, the, finally has to decide

230
00:21:40,387 --> 00:21:45,267
whether the machine accepts while we look
at the final state after the last bid of

231
00:21:45,267 --> 00:21:50,091
input is red and if there's any I'm sorry,
we look at the last set of states after

232
00:21:50,091 --> 00:21:54,631
the last input character is red and if
there's any final state in that set, then

233
00:21:54,631 --> 00:21:58,831
the machine accepts and in this case,
after we read zero, we see that in

234
00:21:58,831 --> 00:22:03,314
accepting state c is in the set of
possible states. So what that means is, if

235
00:22:03,314 --> 00:22:07,967
there was some sort of choices that the
machine could make, that we'll get it into

236
00:22:07,967 --> 00:22:12,540
the final state at the end of the input
and so with the machine. Accepts this

237
00:22:12,540 --> 00:22:18,324
input, okay? So if there's a final state
in the final set of possible states, then

238
00:22:18,324 --> 00:22:24,289
the Nondeterministic machine accepts. It
turns out that NFA's and DFA's are

239
00:22:24,289 --> 00:22:29,110
recognized exactly the same languages and
particularly the regular languages. So

240
00:22:29,110 --> 00:22:33,690
NFA's, DFA's and regular expressions all
have equivalent power. They can only

241
00:22:33,690 --> 00:22:38,390
specify regular languages. Dfa's are
definitely faster to execute primarily or

242
00:22:38,390 --> 00:22:43,452
entirely because there are no choices to
consider so a DFA and just follow a single

243
00:22:43,452 --> 00:22:48,333
path through the state graph where with
NFA we have to keep track potentially of

244
00:22:48,333 --> 00:22:53,539
the set of choices in the NFA and we might
be in set of states. However there are

245
00:22:53,539 --> 00:22:59,679
some advantages to NFA so they are in
general much smaller. And DFA's, In fact,

246
00:22:59,679 --> 00:23:08,612
they can be exponentially smaller so the
smallest. Nfa, Maybe much, much smaller

247
00:23:08,861 --> 00:23:14,920
than the smallest equivalent DFA for the
same language, And, there's, so

248
00:23:14,920 --> 00:23:22,141
essentially there's a space time tradeoff
between NFAs and DFAs. Nfas might be more

249
00:23:22,141 --> 00:23:25,960
compact but DFAs will be faster to
execute.