Welcome back, In this video we're going to
talk about converting regular expressions
into non-deterministic finite automata.
Before we get started I wanna give you an
overview of the plan for the next few
videos. We have a lexical specification
that we want to implement and the first
step is for someone to write that down as
a set of regular expressions. Now that
bites all the courses not implementation,
that's just specification. So we have to
translate that into a program that can
actually do lexical analysis and this
actually happens in several steps. The
first part is a translate Those regular
expressions into non-deterministic finite
automata that recognize the same, exactly
the same thing. And then those
non-deterministic automata are translated
into deterministic automata and finally
those deterministic automata are
implemented as a set of Lookup tables and
a little bit of code for traversing those
tables. So in previous videos, we talked
about this piece and we've also defined
this piece. And so now we're ready to put
the whole thing together and in this
particular video, we're going to focus on
this component right here, The translation
of regular expressions to
non-deterministic finite automata. So the
plan is that for each kind of regular
expression we're going to find an
equivalent Non-deterministic Automata,
automaton that accepts exactly the same
language as the language or a regular
expression. And here's a little bit of
notation we're gonna use. We'll define
these automaton for regular expressions
and usually, what we're going to be doing
is needing to modify their start states
and their final states so we'll just
indicate the start state with the l and
the final state. With the double circle
and we won't worry too much about the
overall structure of the machine as long
as we have a handle on the start state and
the final state. I should say that in the
machines we'll build here, there will only
be one final state. Okay, so let's begin.
So for the epsilon regular expression,
once the machine that accepts that, well
this is a very simple machine. We can just
have a start state and a final state and
epsilon transition between them so this
machine accepts exactly the empty string.
Certainly for a single character A, we can
define a one transition two state machine
that accepts that one character. So from
the start state we can move to the final
state if it only, if we read that
particular character, okay. So those are
out two simple regular expressions and now
we have to do the compound regular
expressions. And these are little
[inaudible] involved. So let's talk about
concatenation first. And so, because we're
gonna build these machines up from
smaller. Regular expressions to larger
ones, we can assume that we've already
converted A and B separately in two
machines. So I have the machine for A. And
to have a machine for B and now all I have
to do is say how I'm going to paste
together these two machines to form a
machine, a compound machine that
recognizes the same language as a
concatenated with B. And here's the
construction, the start state for the
compound machine will be the start state
for A so we'll just keep that start state
for A the same and then we modify the
final state of A. So we make the final
state of A no longer a final state and
I've done that here by removing the double
circle on the final state of A andthe
epsilon transition to the start state of
B. Now if we think about it, that does
exactly the right thing but that says, is
that first you recognize some portion of
the input that belongs to the language of
A, and when we get to that, what would
been the final state of A, we can jump to
the start state of B without consuming any
input and then try to read the rest of the
string as part of the language, as, as a
string in the language of B. And for union
we have a similar way of phasing together
the machines. Although the, the structure
is somewhat different so we, at a new
start state for the compound machine and
What does A + B mean? It means either the
input is in the language of A, or it's in
the language of B. And epsilon transitions
are really good for capturing this because
we just make a decision right from the
start state is the string going to be in
language of A or is it going to be in the
language of B. So we make a
non-deterministic choice and then we read
the string as using that, the automaton
that we chose and if we get to the final
state. Either those machines we can make
the epsilon transition to the new final
state for the compound machine. Now
remember what the notion is of acceptance
for Nondeterministic Automata, you know?
They make these guesses but if there's any
guess that works, then we say that it's in
the language of the machine. So, if in
fact the string is in the union of A or B
then either choosing A or choosing B will
work and so the machine will accept the
string. And finally the most complicated
case for iteration is star, we have the
following construction, So here's the
machine for A, Embedded in here. We've
added a new start state and a new final
state, And now, let's talk about how this
works. So one possibility, if we remember
that epsilon is always in the language of
A<i>, and so we have this transition here,</i>
We can go straight from the start state to
the final state and accept the empty
string. And so, that just guarantees that
the empty string is in the language.
Otherwise, what do we do? Otherwise, we
can make a transition, an epsilon
transition to the start state of A. And
then we can, from the final state of A if
we reach it, we can go back to the start
state of the whole machine and we can do
this as many times as we like. Okay, So,
there's the iteration of A, Surround this
loop right here, And when we reach the
final state of A we can also decide to
just make a transition to the final state
of the machine, we conclude that the last
time. And so this machine recognizes zero
or more strings in the language of A. So
now, let's do an example, So here's a
regular expression and we want to build a
equivalent nondeterministic machine that
recognizes the sa me language and we're
gonna follow our construction, Which works
by induction on the structure of the
regular expressions starting with the
simple regular expressions and building up
to the compound one so what do we have
here? So we have a machine for accepting
one, okay. So we need a machine that
accepts one and if we call it had two
states and it just, you know made a
transition between the two on the number
one, Similarly a machine for accepting
zero. Okay, And now, we need to put them
together in a machine that accepts either
one or zero. And the way we did that is we
made a choice from A, from a start state
for the compound machine where you can
either move to the machine for accepting
one or the machine for accepting zero. And
then we have, at the end, also epsilon
moves back to the final state of the
compound machine. Okay, And now we need to
iterate this so we need to be able to
accept zero or more of one's or zero's and
so we're going to take this entire Block
here and paste it into the pattern that we
had for iteration so how do we do that?
Well, we have a new start state and a new
final state, okay. And there's an epsilon
move from the start state to the new final
state to guarantee that we accept the
empty string. And then we can just iterate
this inner machine as many times as we
like. We can make an epsilon move to the
start state, We could execute the machine
ones and if we decide we want to do it
again, well we can do that. Okay, Go back
around for another time, Or from the final
state, we can decide that we've seen
enough and we can just move to the final
state of the compound machine. So this
machine then accepts the language one +
zero<i>. And now, we have a little bit more</i>
to do. We have to accept, we have other
machine that accepts just one so we build
another machine that accepts The digit one
and now we need to compose two of these
things, to concatenate them and that was
very simple. We just have an epsilon move
from the final state of the first machine
to the start state of the second mac hine
and then these are all the states of the
final machine. And we just need to now
label our final, final state or the end of
the state that we're actually gonna use in
the end of the final state of the entire
machine which should be that one and the
start state, Which is this state over
here. And that's the entire construction
for the non-deterministic automata or a
non-deterministic automata that recognizes
this language.