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

15.1: Nondeterministic Finite Automata
Recap: Nondeterminism
Executing an NFA
Definition of an NFA

Nathan Brunelle and David Evans
University of Virginia
---

Last time, our topic of the day was
nondeterminism.

We introduced this new idea for how we
could talk about finite state automata,

where we essentially just relaxed what we
could do with them.

And this idea of nondeterminism,
this is going to come up again when we

talk about Turing
machines, we're going to be

talking about
nondeterminism all over again.

So it's important to learn this for that
reason.

Also, when we're talking about finite
state automata, these nondeterministic

versions, these are actually the most
useful finite state automata.

So far, we've been discussing this idea
that regular expressions and finite state

automata are kind of equivalent as models
of computing.

Anything I could do with one, I could do
with another.

And in particular, my goal here is to show
how I can convert any regular expression

into a finite state automaton for that
same language.

When we do this in sort of the most naive
way, as we start showing how we can do

this transformation from regular
expressions to finite state automata,

what we're going to
end up with is going to

be a nondeterministic
finite state automaton.

It's easiest to take a regular
expression and convert it into

a nondeterministic automaton
because of that relationship.

Since regular expressions and
nondeterministic automata are sort of more

closely related to one
another, the nondeterministic

ones are the ones that
people typically use.

To sort of show you what progress we've
made so far with this proof to show that

finite state automata are regular
expressions, our goal has basically been

to show how I could convert
a regular expression, any

regular expression, into
a finite state automaton.

That's been our goal so far.

Our strategy for doing this has been to,
first of all, recognize that these

operations, so epsilon, literal
characters, unions, concatenations,

and clini-star, those
operations gave us the

rules for how to build
a regular expression.

That's how we defined
a regular expression

is just anything we
can do with these rules.

What we've been doing so far is we've been
using this idea that computability by a

finite state automaton is going to be
closed.

Under all of those same operations.

All those things we can do to
build a finite state automaton

are things that we can sort
of do to finite state automata.

So that if we show that we can do each of
these things to a finite state automaton,

then since these were rules for how to
build a regular expression, we could take

those same rules to build a finite state
automaton for the same language.

So far, we've already
shown that we can do

the empty string as a
finite state automaton.

We can do a literal as a finite state
automaton.

And last class, we showed that we could do
union as a finite state automaton as well.

The things that we have left to do are
concatenation and then also the quainy star.

Last class, we started
talking about these finite state

automata that we called
non-deterministic finite state automata.

And basically, the whole idea of
discussing non-determinism is that it's

going to make this demonstration of
closure much easier.

So we were able to do these first two
without a huge amount of difficulty,

at least, staying with deterministic
finite state automata.

If we instead relax ourselves so that we
have non-deterministic finite state

automata, concatenation and star are going
to be massively easier.

So we're going to stick to non-determinism
for those.

A non-deterministic machine, though, is
equivalent in power to a deterministic one.

We haven't shown that yet, but that is the
case, that a non-deterministic machine has

equivalent computing power to a
deterministic machine.

So if I can show that I can convert any
regular expression to a non-deterministic

machine, I could convert that
non-deterministic machine into a

deterministic one if I really needed to or
wanted to.

So this is kind of like this idea that we
showed NAND circuits.

Were equal to and or not circuits, which
were equal to and or not straight line.

And then we could conclude
that NAND circuits are

therefore equivalent to
and or not straight line.

Since A is equivalent to B, which is
equivalent to C, and equivalence is

transitive, we can
conclude that the first

one and the third one
are equivalent as well.

We're doing a similar thing here.

I'm going to show that I can convert
regular expressions to non-deterministic

finite state Automata,
which can be converted

into deterministic
finite state automata.

So they're all equivalent.

So just as a reminder, these are our
pieces of a regular expression.

And we've already shown that these can
become a finite state automata.

In particular, we showed that they could
become a DFA.

So that's where we're at so far.

So we've yet to do concatenation in
Queenie Star.

So as a reminder of what we meant by
non-determinism.

So by non-determinism, we had some sort of
relaxation for what our automata could do,

where with deterministic
finite state automata, we

said we had to be in
exactly one state at a time.

And from each state,
we could have exactly

one transition per
character for that state.

With our non-deterministic
finite state automata, we can

be in any number of states
at a time that we would like.

So we could be in zero of them or all of
them or any combination in between.

I'm allowed to have multiple or zero
transitions matching I'm also going to

allow you to make transitions that don't
consume characters.

So you can just say, you
can jump from this state to

that state without using any
characters from your input.

And the idea was
essentially that if I was trying

to figure out, can I get
to my friend's house?

Or is there some path through these roads
to get me from here to my friend's house?

And I came to some fork in the road,
and I didn't know which way to go.

The non-deterministic approach is to say,
let's take both of them.

So we can sort of split the
universe in two, where in one

universe I go left and in
the other universe I go right.

And then maybe once I
find my friend's house, I just

pick that's the universe
that I wanted to be in.

So that's sort of how non-determinism
works intuitively.

And we gave not quite this example,
but something very much like this example

in class last time of a non-deterministic
machine.

So this machine will return
one for all of the strings,

such that their second
to last character is a one.

We're just going to do a sample
execution through this automaton

so you can sort of see
exactly what's going on with it.

So the string that I'm going to do is
11010 is what we're going to do.

So I'm going to do a sample
execution with this string so that

we can sort of see how these
automata work more precisely.

So to start with, before I
use any characters from the

input, I'm going to start
out in some set of states.

Non-deterministic finite
state automata, they're

not in a state, they're
in a set of states instead.

What is the set of states that I'm in
before I read any characters from my input?

Yeah, I'm just in the start state.

So the only state that I'm in is the start
state.

So we always start out in the start state.

If we had transitions from
the start state that didn't require

me to read any of the input,
I would be in those as well.

This machine does not have any such
transitions, so we don't do that.

So the next thing I'm going to do is I'm
going to read that one.

The first character in my input,
that is a one.

So I'm going to transition on a one to
some new set of states.

So what's going to happen is we know that
we're in the start state.

And one of the things that
the start state transitions

to, we can get to by sort
of following that self-loop.

So that self-loop matches on a one.

So from the start state, we also
transition into the start state on a one.

Additionally, the start state transitioned
on a one to the state one.

So I'm just going to represent that with
an O, let's say.

So now after we've read
that one character of one,

we're in both start as well
as the middle state there.

So then the next thing we're going to do,
I'm going to read another one.

So when we read that
second one, well, the start

state transitions to
the start state on a one.

And then the start state also transitions
to state one on a one.

And then state one on a one transitions to
next.

So I go from the set
of states, start one, and

go to start one next
when I see a one as input.

So then the next thing we're going to do
is we're going to receive a zero as input.

So on a zero, the start state goes to the
start state on a zero.

On a zero, though, the start state does
not go to state one.

That did not match.

So the start state does not go to state
one.

State one on a zero goes to next.

So state one is going to go to next.

Next, though, on a zero doesn't have any
transitions that matches.

So sort of this next state doesn't
transition anywhere.

So there is just no continuation of that
path on a zero.

So the next state does not go anywhere.

So now we're in the state S with N.

And then the next thing we're going to do
is we're going to transition on a one.

So S is going to go to state S on a one,
as well as state O on a one.

N has no transitions on a one,
so it doesn't go anywhere.

So now we're just in SO.

If we were to stop here...

If we didn't have that 0 as our last
character, if we stopped there

would we return 1 or would we return 0?

0.

Why?

I can answer that.

Why?

Right.

So our rule for when we return 0 is we
return 0

if any of the states we are currently in
are 0.

The start state, that is not a final
state.

1 is not a final state, so none of the
states...

We're currently in our final states,
so therefore we return zero.

We do have one more character though,
actually, so that is that zero.

So on a zero, the start state transitions
to the start state.

State one transitions to the next state.

So start transitions to start,
one transitions to next.

So now we're in start and next.

So now we've read our last character.

Do we return one or do we return zero?

One.

Why one?

Right, because this one was a final state.

So therefore, we return one.

Since among the states that we were in,
one of them was a final state,

we return one.

So we return one for this string,
its second to last character is a one.

That's what we hoped for.

So this is basically our definition for a
non-deterministic finite state automaton.

So like with our deterministic one,
we write one down by giving some finite

number of states, one of which is a start
state and some of those are final.

So that's exactly the same thing that we
had for the deterministic automata.

The main difference is going
to be what transitions look

like and how we determine
what to return for these automata.

So those are going to be the main
differences with the deterministic automata.

So our transitions before
were just going to be some

function that mapped state
character pairs to some state.

You took a state, you
took a character, and

then you had one state
that was your next thing.

In this case, instead of having just a
function that maps states and characters

to single states, we're going to have a
function that is perhaps a partial function.

So we're allowed to say some state
character pairs don't have any transitions.

That's what that means to be a partial
function.

So we're going to have a function that
might be partial.

There are some inputs for which we won't
have outputs.

That's going to map pairs of states with
characters or epsilon for empty,

for those empty transitions.

That is transitions that don't consume
input.

The output of that function is going to be
a set of states.

So you can go into multiple states
instead.

So it's a function
mapping states paired with

characters or epsilon
to a set of states instead.

So with this in mind, what our execution
rule looks like is we're going to first

begin in our start state, in our initial
state.

And then we're going to
enter every single state that I

can reach without consuming
input from that start state.

So if I had my start state, and then I had
some transition that didn't use any input

to my next state, then once I entered this
start state, I would also be in the next

state, because I didn't need any input to
get there.

So we begin in the start state.

We're also in every state that I can reach
without consuming input.

And then just like before,
we're going to read our input

one character at a time
without being able to look back.

And we're going to transition into new
states, plural, potentially, once per

character, based on
which states, plural, I

am currently in and
which character I see.

And then once I transition to
new states, I'm also going to

transition into states reachable
without consuming input.

And then I return true if any state I end
in is final state, and return false if

every state I end in is non-final,
is the definition here.

So basically, the main
difference is that I can

have multiple outgoing
transitions per input.

So what I do is I just take all
transitions for all states I'm currently

in, and then I just sort
of spread out to all the

states I can get to without
consuming input from there.

And I repeat that over and over and over
again.