Welcome back. In this video we're going to
talk about finite automata
which we'll see in future videos are a
good implementation model for regular
expressions. So in the last few videos,
we've been talking about regular
expressions which we use as the
specification language for lexical
analysis. And, in this video we're gonna
start something new. We're gonna talking
about Finite Automata which are the For a
convenience as an implementation mechanism
for regular expressions. And so regular
expressions and finite automaton are very
close related. It turns out that they can
specify exactly the same languages called
the regular languages. We won't prove that
in this course but we'll certainly make
use of that fact. So, moving right along,
What is a finite automaton? Well, here is
a typical definition as you might see in a
automaton theory textbook. Finite
automaton consists of an input alphabet.
So, it's a set of characters that it can
read. It has this finite set of states. We
should probably emphasize that. This is
what makes it a finite automaton is that
it has some set of states that it can be
in. One of those states is special and
it's designated as the start state. Some
subset of the states are accepting states
so these are the states that. But, well,
we'll just find that more in a minute but
intuitively, if the automaton terminates,
after reading some input on one of these
takes that it accepts the input.
Otherwise, it rejects the input and
finally the automaton has some set of
state transitions that is in one state,
they can read some input and go to another
state. So let's look at that little more
detail so a transition in a finite
automaton. If I'm in, in this case I've
written out one particular transition
here. We're in state one and we read the
input A then, the automaton can move to
state two, okay. And there could be lots
of different transitions for the automaton
from different states and different inputs
and its read the following way. If we're
in state one on input A , we would go to
state two. And, if the automaton ends in
an accepting state when it gets to the end
of the input that is going to do what's
called accepting the string Meaning that
it will say yes, That string was in the
language of this machine. So intuitively
the automaton starts in the start date and
it repeatedly reads inputs one input
character at a time makes a transition. So
it'll see what kind of transition it can
make out of its current state based on
that input to another state and if that's
done ringing the input it's in one of the
final states that it will accept.
Otherwise is going to reject the input.
Now, one of the situations in which it
rejects, well, if it terminates In a state
S, that's no one of the final or accepting
states, okay? So that ends in any other
state besides one of the accepting states
and it's going to reject. If the machine
gets stuck, Meaning it finds itself in a
state and there's no transition of that
state on the input. So in particular,
let's say that in some state as a news and
the input is A, and there's no transition.
There's no transition specified per state
as an input A so the machine can't move
anywhere and it get stuck and that's also
a rejecting state. And so in these two
situations, if, if you either get to the
end of the input and it's not in a final
state or. If it never reaches the end of
the input because it can stuck and both of
those cases it rejects the string. That
string is not in the language of the
finite automaton. Now there's an
alternative notation for Finite Automata
that I think is more intuitive for
examples and so we're going to emphasize
that way of writing the mount. In this
notation a state is represented as a known
graph which just draws a big circle. The
start state is represented as a node that
has an edge or an arrow into it with no
source. So, this is a transition into the
node but no source node that it comes from
and that indicates the unique start state.
An accepting state is drawn as a node wit
h just double circles like this. And
finally a transition is drawn as an edge
between two nodes of the graph. So with
this as the time in this state that I'm
circling in blue and I read the input a
well then I can move to this state at, at
the tail of the arrow. So now, let's do a
simple example. Let's try to write up the
automaton that accepts only the single
digit one. So all we need is start state.
And will probably want an accepting state
as well and now the questions is what do
we put in between the two? Well, there
would be some kind of transition here and
it's a good guess that we should take that
transition if the machine reads the one.
Now let me take a moment here to talk
about how the machine executes so let's
label these states. Let's call this state
a and let's call this state b, okay. So
the machine will have some input. Okay,
and we can write that input out will be
here. So let's just say, we have the
single character one and it begins in some
state namely the start state. And so, one
configuration of the machine is the state
that it is in And the input. And typically
we would indicate where it is in the input
by just a pointers saying what position it
is in the input. And, the important thing
to know about input in [inaudible] the
input pointer always advances. So, when
we, or it only advances so when we read a
character input, the input pointer moves
to the right and it never moves back.
Alright, So from state a, we have a rule.
We can see that we're in state a. The next
input character is a one and that allows
us to take a transition to state b and so
now where b in state b and where as our
input point well it's beyond the end of
the input indicating we are at the end of
the input. And so now this is. We are in
an accepting state and we pass the end of
the input and so we accept. Okay? So
let's, do another execution. So we start
in state a and let's take as our input the
string zero. Okay. And I'd like to draw
the pointer. Actually I should have drawn
it before the input so we'll al ways put
the pointer between two input elements. In
this case it's a merely to the left of the
one we're about to read. So in this case
we're about read zero so in state a. Our
input is zero. We look at our machine. We
see that there is no transition on zero.
All right? And so the machine stays stuck.
It doesn't make any move at all and this
is our final configuration. And we could
see that we're not at the end of the input
and so this is a reject. Okay, so in this
case the machine rejects that string as
not being in the language of the machine.
Let's do one more example. Let's say that
we're in state, well we're always
beginning in state a and the start state,
and let's say our input this time is the
string ten, okay? And our input pointer is
there. All right? So again we're in state
a. The input is a one and so we'll move to
state b. And now the input doesn't change.
Just the input point changes but I'll just
copy the input over to show the
difference. Now the input pointer has
advanced cuz we've read one character of
input and now we're in another state. And
now we can see that we're in state b. Our
next input is zero and there is no
transition on zero from state b and so
even though we're in an accepting state, b
as a final state, it's one of the accept
state and we haven't consumed the entire
input. And so this, The machine also
rejects this string so this is also a
reject. And in general we can talk about
the language. Of a finite automata that is
equal to the set of...accepted strings.
Okay? So the language of a finite
automaton, when I'm talking about the
language of a finite automaton, I mean the
set of strings that the automaton accepts.
So now let's do a more complex example.
Let's try to write out an automaton that
accepts any number of one followed by a
single zero. So once again well need a
start state and we'll also need a final
state and now let's start by thinking
about what's the shortest string is that's
in the language of this machine. So in
this case, we know it has to end in a
singl e zero. So a zero definitely has to
be, a zero transition has to be the last
move and before that zero can come any
number of what? In a particular there
could be no 1's. So one transition in this
machine is that from start state on input
zero we can definitely go to the final
state because the single string consisting
of a single zero isn't the language of
this machine. And now the only question is
how do we encode the fact that any number
of 1's can proceed to zero? Well, there is
an easy way to do that. We can just add a
[inaudible] by the start state. And take
that transition if we read at one. And
what does this mean? This means that we'll
stay in the state, state as longer are
we're reading 1's and as soon as we read
zero, we'll move to the final state
because that has to be the end of the
string if the machine is going to accept
it. So let's do a couple of examples to
convince ourselves that this works. Let me
label this state?s again. So this is state
a, and that's stat b. So Let's write out
here states and input. So we'll begin in
state a and let's take as input 110, okay.
So let's do an accepting case first. All
right, So our input pointer begins to the
left of the first character. So, we're in
state a in start state. We're reading a
one and that says we should take a
transition that puts us back in state a.
And so, we advance the input pointer. And
now we consume the first one and, and
again we're in state a and the next input
is a one so we'll make another transition
to state a. And the input cleaner will
advance. So now we're in state a and the
next input is a zero and so we'll take the
transition to b and now in this
configuration, so the input pointer has
reached the end of the input we're in an
accepting state and so the machine
accepts. 110 is in the language of this
machine. So now let's do an example where
we will reject the input. And what
configuration do we begin in and again a
configuration for a finite automaton that
just means you know a point in the
execution it alwa ys consist of a state
and a position of the, the input pointer.
So our initial state is a and now let's
just choose the string. I don't know,
let's take 100 and let's confirm that this
is not in the language of the machine. All
right, So we begin in state a and our
input pointer is there. Now we read a one
and that means, well, you know. So it's
from state a transition of one. We stay in
state a and the input pointer advances.
And now we see a zero. So from state a and
input zero, we make a transition to state
b. And now the input point is here so now,
we're in state b and we have an input of
zero but there is no transition the b and
zero, there are no transitions out of b at
all and so the machine gets stuck, it
can't get to the en of the input and
again, even though we're in an accepting
state we haven't read the entire input yet
and so that means the machine will reject.
And so, 100 is not in the language of this
machine. Up to this point a finite
automaton consumes a character of input
every time it makes a move. So if you
can't make any move at all, the input
pointer advances. Now we're talking about
a new kind of move, the epsilon move and
the idea behind the epsilon move is that
the machine can make a state transition
without consuming input, So for example if
I have my states and I'm in state A and my
input. And let's just say that we have x1,
x2, x3 and for some reason we're about to
read x2. When we make an Epsilon move the
machine changes state but the input
pointer stays in exactly the same place.
So the new configuration of the machine
that reinstate b, but our input pointer is
still waiting to meet x2. So, you can
think of an epsilon move is a kind of free
move from the machine it can, it can move
to a different state without consuming any
input. And just to be clear here the
machine does not have to make the epsilon
move. It's a choice so they can decide
whether to make the epsilon move or not.
Now epsilon move, the first time we have
mentioned the possibility that a finite
automata might have a choice and what
moves it makes. There's actually an
important distinction between automata
that have choices and those have don't. So
deterministic finite automata have two
properties, first of all, they have no
epsilon moves so they must always consumed
input. And second, they only have one
transition per input per state. What do I
mean by that? That means that if I look at
any state in the deterministic automaton,
they can never have something like this
where they have two possible moves for the
same input. All the outgoing edges in the
deterministic automaton must have
different input labels. And then
Nondeterministic Finite Automata are just
those not deterministic. So in particular
a Nondeterministic Automata can have
epsilon moves so it can choose to move to
another state without consuming input and
it could also have multiple transitions
for one input in a given state so
something like this, is okay for a
Nondeterministic Automata. Yeah. Let me
just point out really epsilon moves are
enough to create a non-deterministic
automata and then at the second case where
you have multiple transitions on the same
input can be simulated just by a slightly
more complicated machine with epsilon move
so for example I can draw this machine in
the following way. I can have or I can
simulate the machine that circled there in
the following way. I can have a state with
two epsilon moves and then. Each of those
states has a move on A so I were to label
the states one, two, and three. Then this
would be the state that corresponds to
one. And this would be the state that
corresponds to two and this state be, be
the state that corresponds to three. So
anytime that we have multiple moves out of
the state on a single input we could
always replace that by a few more states
with epsilon moves and have every state in
the machine only have a single transition
for every possible input. So really the
only fundamental difference between the
deterministic automata and
non-deterministic automata is w hether
they have epsilon moves or not. A key
property of a Deterministic Automata is
that it can only take one path through the
state graph per input. So this is per
input. What do I mean by that? Well, the
automaton always begins at the start state
and let's take a very simple input string
like ABC and if we can look at the
sequence of states that the Deterministic
Automaton will take, For that input, this
path through the state graph is completely
determined by the input because again it
has no choice. In a given state, this can
be one transition label day and this
continue to a state that it only has one
transition labeled b and that goes to
another state that only has one transition
labeled c. And so, every input determines
the path through the state graph of the
automata will take. And, this is not true
for Nondeterministic Automata. So, it
might be for example. That beginning in
the start state and on input a that there
is some state I can go to on that input a
but there maybe another transition labeled
a that would take me to a different state
so the automaton might be able to go to
one of two different states and again
there might be also epsilon transitions.
And so what happens with Nondeterministic
Automata is that in general as they
proceed to the state graph is they execute
on the input, they could wind up in any
number of different states. Okay. And the
rule with the non-deterministic automaton
about when it accepts is that it accepts
if any path accepts. So if NFA Accepts, If
some Choices Lead to an accepting state at
the end of the input. Now there's a
[inaudible] automaton, I can choose what
move to make and as long as there are some
choice it can make, then we'll get it to
an accepting state. So let's say switching
colors here that you know this was an
accepting state down here and they took
this path. Then it would accept and maybe
all of these other pass are rejecting
pass, that doesn't matter. As long as
there is one path, a one set of choices
the NFA could make to get it to an
accepting state at the end of the input,
then we say that, that string is in the
language of the NFA. The fact that NFAs
could get into multiple different states
depending on the choices they make during
a run is important and will actually play
central role in the future video, so we're
gonna do a quick example here to just make
sure that this is clear. So here's a
little automaton and note that it is
Nondeterministic Automata from the start
state there are two possible moves input
zero. And what we're going to do is just
walk through in execution of this machine
on a sample input and see what different
states it can get into. So we begin at the
start state and we should probably label
our states actually so that we can refer
to them. Let's call them A, B, and C. And
let's say at the first input is one and so
what does that mean? That means we'll take
this transition. We'll just go from the
start state and come back to the start
state and so the set of states that the
machine could be in after the first
transition is just the set A. So it's
guaranteed to still be in the start state.
So there's no, no choices with the first
move. Now let's say at the second input
character is a zero and now we do have a
choice. We could either go to state B or
we could go to state A. And, we could
think of this then as a set of
possibilities that after we execute this
move, this transition, the machine could
be in anyone of the set of states and
actually this completely characterizes the
possibilities for the machine. We've only
read the second input character and now we
could be in a set of states, okay? And we
could be either in state a or in state b.
And so now let's say we read another zero.
And where could we go then, well if we're
in state B we could make the transition to
state C but if we're in state A then we'll
make the transition either to state B or
again to state A. So in fact we could be
in anyone of the three states if we read
another zero. Okay? And now you, I think
you can see w hat the rule is. So in every
step a Nondeterministic Automata is in a
set of states of the machine and when it
reason, the input we consider all the
possible moves it can make to compute the
complete set of states that could be in at
the next step of the machine. Okay? And
then the, the, finally has to decide
whether the machine accepts while we look
at the final state after the last bid of
input is red and if there's any I'm sorry,
we look at the last set of states after
the last input character is red and if
there's any final state in that set, then
the machine accepts and in this case,
after we read zero, we see that in
accepting state c is in the set of
possible states. So what that means is, if
there was some sort of choices that the
machine could make, that we'll get it into
the final state at the end of the input
and so with the machine. Accepts this
input, okay? So if there's a final state
in the final set of possible states, then
the Nondeterministic machine accepts. It
turns out that NFA's and DFA's are
recognized exactly the same languages and
particularly the regular languages. So
NFA's, DFA's and regular expressions all
have equivalent power. They can only
specify regular languages. Dfa's are
definitely faster to execute primarily or
entirely because there are no choices to
consider so a DFA and just follow a single
path through the state graph where with
NFA we have to keep track potentially of
the set of choices in the NFA and we might
be in set of states. However there are
some advantages to NFA so they are in
general much smaller. And DFA's, In fact,
they can be exponentially smaller so the
smallest. Nfa, Maybe much, much smaller
than the smallest equivalent DFA for the
same language, And, there's, so
essentially there's a space time tradeoff
between NFAs and DFAs. Nfas might be more
compact but DFAs will be faster to
execute.