---
Video Title: Nondeterminism
Description: Theory of Computation
https://uvatoc.github.io/week7

14.5: Nondeterminism

Nathan Brunelle and David Evans
University of Virginia
---

We're going to talk about non-determinism.

Keeping in mind, our ultimate goal is to
show that anything we can do with a

regular expression, we can do with a
finite state automata.

That's our ultimate goal.

Doing these proofs like the union thing
for the next batches of operations is

going to get really,
really, really difficult if

we stick with our current
finite state automata.

So we're going to relax what our finite
state automata can do a little bit in

order to make it easier to prove the rest
of these operations.

And the way that we're going to relax them
is using non-determinism.

So we're going to relax them using
non-determinism.

So we're going to be
talking next about this idea

of a non-deterministic
finite state automaton.

The ones we've been looking at so far have
been deterministic finite state automata.

Deterministic in this sense means they're
only ever in one state at a time.

They're always in exactly one state at a
time.

When you're in some state, there's only
one state that could be your next state.

With these non-deterministic
finite state automata, we're going

to say that you can actually
be in multiple states at once.

It turns out this is not going to be a
more powerful kind of machine.

Everything I could do
with non-deterministic finite

state automata, I can do
with deterministic ones as well.

We're going to show that next class.

But they are equivalent.

This just allows us a
little bit more flexibility

as we actually draw or
write down our automata.

All right.

So, so far with our
automata, we can have

exactly one transition
per character per state.

So our rule with our finite state automata
so far has been every state must have

exactly one outgoing transition per
character.

And we're only ever allowed to be in one
state at a time.

The difference we're going to have with
non-deterministic finite state automata is

you can be in any subset of your states at
a time.

So you can be in any number of states at
all at a time.

So I can be in five states at a time.

I can be in two states at a time.

I could be in one state at a time.

I could be in all the states at a time.

I can be in none of the states.

Any arbitrary subset of the states is
allowable with this, not just one state at

a time like we had with the deterministic
ones.

We're also going to be
allowed to have multiple

outgoing transitions from
one state for a character.

So we're going to be able
to have some state where we

say, go to that state as
well as that state on a zero.

So we're allowed to have multiple outgoing
transitions for some character.

So we can say, like, let's take this state
and on a zero, you go into both of these

other states is the way that's going to
look.

You have multiple outgoing transitions.

We can also take transitions
without consuming a character

at all, without needing
to use a character at all.

So these are something that we're going to
call epsilon transitions.

So if I have an epsilon transition,
this says that in order to take this

transition, I don't need to have any
input.

I don't need to look at any input to do
that.

It just means whenever I enter this state,
I also have entered that state.

So whenever I've entered that first state,
I'm also going to be in that next state.

So if I have some transition on like an A
or something that goes to that middle

state there, what this is saying is that
if I'm in this state and I receive an A,

then next I'm going to be in both of these
two other states.

It's going to be convenient to do this.

But yes, in this case, I could do the same
thing.

I could have the same behavior by just
having two outgoing A's in this case.

To give you an idea or to give you an
intuition for exactly what what

non-determinism is trying to do or why this
is sort of a this might be a helpful thing.

Let's say that you're you're trying to
drive to your friend's house.

So imagine that, I don't know,
it's post-apocalyptic world.

You're driving to your friend's house.

Cell phones are dead.

There's no GPS.

The only thing is you, your car and your
friend at his house.

Your friend has given you some directions
to his house.

But you come to a fork in the road that's
not mentioned on the directions.

Which way do you go?

So there's your friend's house.

You're trying to get there.

There is you on your car.

And you at some point come to this fork in
the road.

And you want to know which way is the
correct way to go on that fork in the road

to actually get you to your friend's
house.

How could you do that?

Okay, so maybe you
want to go left because

it looks like the house
is vaguely leftward.

The words are in the way of the left.

So you want to go to the right.

How did you know that the words blocked the
way of the left before you took the left?

Yeah, okay.

So you could take the left and see if any
words block your way.

And if so, you can turn around and take
the right.

All right.

Yeah.

Yeah.

So you could do some sort of backtracking
where you could go left for a while and be

like, I'm pretty sure I
should have been there

by now and then turn
around and try to backtrack.

But then you might end up with this issue
where what if you took the left and there

was another couple of forks in the road
that weren't mentioned.

And then those forks had forks and the
forks had forks had forks and so forth.

And now you've got a whole drawer full of
forks.

What are you going to do?

Yeah, so the non-deterministic solution to
this is you say, take both ways at once.

So why not both?

So that would be great.

If we could do that,
if we could just take

both ways at once, that
would be super great.

If I just said, like, I don't know,
I'm going to split reality in two,

and in one reality I'm going to take the
left fork, and in the other reality I'm

going to take the right fork, and the
first one to arrive at the friend's house

is going to be the reality I choose to
live in.

So that is the non-deterministic approach
to this, is whenever there is some choice

for which way to go, and it's not totally
obvious which choice to pick, try both.

And whichever one gets you the right thing,
that's going to be the one that you do.

That's the only reality that's going to
matter.

So if you have forks, and then you have
forks on forks, and forks on forks on

forks, then you're just going to be
splitting reality all these different

times, exploring all of
these realities in parallel, until

you find the reality that gets
you to your friend's house.

And then you say, yeah, the directions got
me to my friend's house.

So this is non-determinism.

I'm going to give you an
example now of a non-deterministic

finite state automaton It's
going to behave in this way.

So this non-deterministic finite state
automaton is going to be computing this

language third last
one, which says my third

from last character
in my string is a one.

So I want this to return
one or to return true for any

string such that its third
from last character is a one.

So let's think about exactly what we might
want this machine to look like.

So certainly we want the path to some
final state saying if I saw a one and then

I saw some other character
and then I saw some

other character, then
I want to return one.

What we want the end of the road to look
like.

We're expecting the end of the road to
look like this.

That once I see a one, if I saw two more
characters and then I was done,

we want to return one.

The problem here, though,
is how do I know that I

wasn't going to have more
characters after this one?

How did I know when I took the transition
for this one here that that was definitely

going to be the third from last character
in this string?

So in order to do that, I'm going to call
this one the start state, and I'm just

going to make a transition that goes from
that state to itself on zero and one.

So we're going to say, I don't know.

I don't know when I
look at a one whether or

not it's going to be the
next to last character.

So I don't know whether I
should wait for more characters

before I consider that one to
be the third from last character.

Or whether I should say that's going to be
the third from last character.

Let me make sure there's only two more
after it.

So I don't know which one to do.

I'm going to take both forks in the road.

So what this transition
is doing is it's saying

whenever I get a one, I'm
going to end up in two states.

I'm going to transition
right on a one, but then

I'm also going to say it
stay in the same place.

So staying in the same place is me
basically saying, don't think that that

one that I just saw is the third from last
one.

So I'm going to wait for more before I
start marching to the right.

Going to the right is saying, yeah,
I think that that one that I just saw,

I think that's going to be the third from
last character.

I just want to show you an example of this
automaton in action.

So the way that this is going to look is
if I have like one, one, one, zero,

one, let's say.

We want this to be in
the language because this

is the third from last
character and it's a one.

So let's see why this finite state automaton
is going to return one for this string.

So to start with, we're in just this state
here.

And the first thing we do is we read this
one.

And what do we do with this one?

We stay in the same state and we move to
the next state.

So we're in both of these two states.

And then we're going to read another one.

So what am I going to do?

Well, this state, it's going to transition
back to itself.

So we're going to be in this state still.

This state is also going to transition to
this one.

So we're still going to be in this state.

And then this state, the
second state, is going

to transition to the
third state on the one.

So now we're in these three states.

Then we're going to read the next one.

So this first state, that's
going to transition to

itself, so we're going
to stay in the first state.

The second state, we're
going to be in because we

transitioned from the first
state to the second state.

The third state, we're still
going to be in that state because

we transitioned from the
second state into the third state.

And then the third state is going to
transition into the fourth state.

So now we're in all of the states all at
once.

Next, we're going to do the zero.

The first state is going to transition to
itself on the zero.

The first state, though, this time does not
transition to the second state on a zero.

It only did that on a one, so we're
actually no longer in the second state.

The second state, though, we were in that
second state before, so we're going to

take that one transition
that we saw in the

second state, and we
end up in the third state.

And then this third state,
it was going to transition

to the fourth state, so
we're in the fourth state.

But we were in the fourth state before.

The fourth state didn't have any outgoing
transitions, so it didn't go anywhere.

That path just sort of died, so to speak.

And then we're going to read the last
character.

So we have one.

So the first state goes
back to itself on one,

and it's going to transition
to the second state.

We were not in the second
state before, so we're

not going to end up
being in that third state.

We were in the third state before,
so we end up in the fourth state.

The fourth state path, that one died.

So now we've read all of our
input and we ask the question,

is at least one of the
states we're in A final state.

Yes, so we return one.