---
Video Title: Equivalence of NFAs and DFAs
Description: Theory of Computation
https://uvatoc.github.io/week7

15.2: Equivalence of NFAs and DFAs

Nathan Brunelle and David Evans
University of Virginia
---

Next, we are going to show that anything I
can do with a non-deterministic finite

state automaton is also
going to be something I

can do with a deterministic
finite state automaton.

So they are equivalent models of
computing.

So to do this, we have to do two steps.

We have to show that anything I can do
with a deterministic finite state

automaton, I can also do with a
non-deterministic finite state automaton.

So we want to know, can
we convert a deterministic

finite state automaton into
a non-deterministic one?

Does anybody have any ideas for how we can
do this?

Yeah, so a deterministic finite state
automaton is a special case.

A non-deterministic finite state
automaton.

So every deterministic finite state
automaton is already a non-deterministic one.

Non-determinism was basically a relaxation
of what our automaton could do.

So a deterministic one just
chooses not to use all of its power,

but it still totally makes sense
as a non-deterministic one.

It just didn't use the non-determinism
available to it.

So every deterministic finite state
automaton is already a non-deterministic one.

No conversion necessary.

It's kind of like saying, can
you convert any circuit that

uses ors and nots into one
that uses ands ors and nots?

It's like, well, yeah, it already is,
because if we were allowed to use ors and

nots before, and now you're
letting me use ands, well, I

didn't have to use the ands
for it to be an and or not circuit.

So every DFA, that's already an NFA.

So we know that NFAs are at least as
powerful as DFA's.

It turns out, though, that any NFA can be
converted into a DFA.

And the strategy we can
use for this is very similar to

that cross-product construction
that we did in last class.

So last class, we had this cross-product
construction, where we said we could make

some new machine that played the role of
two other machines looking at the same

input at the same time, kind of in
lockstep.

By saying that in this new machine,
every state was going to represent a pair

of states, where the first
one came from the first

machine, the second one
came from the second machine.

So we're going to have a similar strategy
to that, where we have super states,

where each state is going to represent
multiple states from the other machine.

Where in this case, each of those super
states is going to be a subset of states.

Yes.

Yes.

Yes, this is just a power set.

So we call this one the power set
construction, in fact.

Also, sometimes the subset construction.

Our strategy for this time is,
we know even though our non-deterministic

finite state automaton
can be in a set of states at a

time, it can only be in
one set of states at a time.

So if we have states
representing sets of states, then

I can only be in one of
those super states at a time.

So we should be able to make it a DFA,
a deterministic one.

So that's the idea.

How can we figure out
how to make being in

one state represent
being in several states?

And the way we're going
to do that is by saying

each state represents
a subset of states.

Let's look at an example of this.

So here's that example we just had.

And what I'm going to do is I'm going to
build an automaton where I have one state

for every different set of states I could
be in.

So in this case, I began with a three
state automaton.

And now I need one state for every subset
of those three states.

So I should have eight states if I did
this right.

That's the size of the power set of a set
of size three.

With three states, I should have two to
the three states after I do the power set.

So I have two to three, which is eight
states down here.

These are the states that my DFA is going
to have.

So now what we can do is we can sort of
just trace through what this

non-deterministic finite state automaton
is going to do.

Keeping in mind that now we have one state
representing a set of states.

What state in this new machine is going to
be my start state?

What state in this new machine will be my
start state?

Yeah, so start is going to be my start
state.

So in this case, it's going
to be my start state plus any

states I could reach from my
start state without using input.

It's going to be my start state.

I can't reach any states besides my start
state without using input.

So in this case, it is just start.

So this one is my start state.

Before we've read any input, I'm only in
one state, that being the start state.

What happens if I get a 0?

If I'm in start and I get a 0,
what happens?

Where do I go?

I am only in the start state.

On 0, start transitions back to start.

What happens if I get a 1?

The start state stays in the start state,
and it moves to 1, so I end up with start1.

Okay, now if I'm in
start1 and I get a 0,

Then one goes to next
and start goes to start.

So we end up in start next if we get a
zero.

If I'm in start one and I get a one,
start goes to start.

Start goes to one, one goes to next.

So we're in start one next and we get a
one.

If I'm in start next and I get a zero,
so start next and I get a zero,

start goes to start and next doesn't go
anywhere.

If I'm in start, next, and I get a 1,
start goes to start and 1.

Next doesn't go anywhere.

So I go to start one on a one.

And then if I'm in start one next,
and I get a zero, and then start goes to

start, one goes to next, next doesn't go
anywhere.

So on a zero, I end up in start next.

And if I get a one,
start goes to start and

one, one goes to next,
next doesn't go anywhere.

So I end up in the same place.

Which ones are my final states?

Yes.

Yeah, so anything with next is going to be
a final state.

So this one's a final state, and this
one's a final state.

And then all of the other states,
I couldn't reach from the start state.

You could leave them in, you could remove
them.

It's not going to impact what your
automaton does.

So this is the idea for how we
can take any non-deterministic

automaton and convert
it into a deterministic one.

Yeah.

It's perfectly fine to
say, all right, this one's a.

This is the final state and
this one is the final state.

You would need to add
transitions to this to make it

a DFA if you are going to
leave the states in there.

Because the rule was
for every state and every

character, you need
to have a next state.

These states that I
have just left empty,

they don't have next
states for any character.

So I need to fill those in for it to
properly be a DFA.

But you could.

It wouldn't change what
the automaton did for

any input, because you
couldn't ever reach them.

But it doesn't hurt to have them either.

Does this make sense?

Cool.

This is now me just
drawing that out by hand

in case I made
mistakes in the last slide.

It should be the same thing.

If we wanted to represent this
symbolically, if I had a non-deterministic

finite state automaton, where I had
states, an alphabet, transitions,

a start state, some final states.

So if this was my non-deterministic one,
then with my deterministic one,

my set of states becomes the power set of
my original set of states.

Because of that, because my
states become the power set of

states, we typically call this
the power set construction.

So we're doing this construction
where our set of states

becomes the power set of
our previous set of states.

So we call it the power set construction.

Our alphabet doesn't change.

We're going to end up with new versions of
all the other stuff, though.

So the first thing we are
going to look at for the other

stuff is which state is
going to be our start state.

Well, our start state is going to be the
set of states.

So each state is a set
of states, remember, so

our start state needs
to be a set of states.

Our start state needs to be the set of
states that contains the original start

state, as well as anything I can reach from
the start state without consuming input.

So the set of states
defined by the start state and

anything reachable from
it without using any input.

So this delta q0 epsilon says look at the
transition function in that DFA.

Look at every place it goes to on the
empty string.

That is without consuming any input.

So the state representing that set of
states is my new start state.

For instance, if this is state one,
and then I had state two there,

and then state three on like zero or
something like that.

Then in this case,
my start state would be

the state representing
the states one and two.

So if our automaton looks something like
that, then when we did our power set

construction, our start state would be the
state representing the set one and two.

Our final states are states representing
any set of states that contains a final one.

So our final states is the set of states
from the power set.

So the set of super
states such that one of

the states in the super
state was a final one.

So all states with a final state in them.

So all states with a final state in them.

And then my transition function basically
says, if I'm in some set of states and I'm

going to transition on some
character, then I want to be in

the state that's just the
union of all those transitions.

The union of the states that any of those
states got me to.

So transition to the state set of
everything any current state transitions to.

So this is just the symbolic version of
this.

If you understand it enough that you could
code it without knowing what all these

crazy Greek symbols mean, then that is
totally okay.

But I know that there are
some people who prefer

to see it in the mathematical
precision like this.