---
Video Title: Power of Deterministic Finite Automata
Description: Theory of Computation
https://uvatoc.github.io/week6

13.1: Power of DFAs
- DFAs can compute some function that cannot be computed by NAND-Circ
- DFAs can compute every finite function

Nathan Brunelle and David Evans
University of Virginia
---

Last time we talked about languages and we
talked about decision problems.

The idea of these is that they are a
different way of thinking about functions.

We also introduced this idea of finite
state automata as this new model of

computing that is suitable for
implementing infinite languages.

In particular, the type of automata that
we talked about last class.

So there are actually several different
kinds of finite state automata.

We've talked about one kind of finite
state automaton so far.

And that's something that we call a
deterministic finite state automaton,

or DFA for short.

Next week, we're going to
be talking about something

called a non-deterministic
finite state automaton.

Just so that you have the formal name for
the thing we've talked about so far,

finite state automata is kind of a
catch-all term for a large category of

things that involve states and
transitions.

In particular, we talked about deterministic
finite state automata last class.

We also talked about how we could use
finite state automata to compute languages.

If I say something like, the language of a
finite state automaton, that means the set

of all strings which that automaton
returned one for.

That is, the language that this finite
state automaton computes, we could say

that's the language of
that finite state automaton,

which is the set of all
strings that it returns one for.

So we introduced finite state automata
last time, and we mentioned that they can

do infinite languages, whereas Boolean
circuits could not.

So what we're going to show today is we're
going to show that not only is it that

finite state automata can do some things
that NAND circuits can't do, we're going

to show that finite state automata can do
everything NAND circuits can and more.

So that is, we're going to show that this
computing model of finite state automata

is strictly more powerful than this
computing model of NAND circuits.

By showing that finite
state automata can

do everything NAND
circuits can do and more.

It says that they're a strictly more
powerful model of computing.

So how can we show
that finite state automata

can do everything that
NAND can do and more?

That it's a strictly more powerful model
of computing?

Suggestions?

Yeah.

We can show how we can maybe convert a
circuit into a finite state automaton.

What else do we need to show?

Yes.

Yes, this first one will end
up showing that finite state

automata are greater than
or equal to NAND circuits.

If we also find one language we can't do
with NAND that we can do with finite state

automata, then that allows
us to conclude that finite

state automata are, say,
strictly more powerful than NAND.

So we're going to show everything NAND can
do, finite state automata could do,

and then we need to
find at least one thing that

finite state automata
can do that NAND can't.

We're going to do that second thing we
listed first.

We're going to show that
there's at least one function

we can do with finite state
automata, but not NAND.

Who can name one?

Yeah, so infinite AND.

I said infinite XOR on the slides,
but infinite AND is just as good.

So we've already done this.

We've already shown that we can do
infinite AND.

NAND circuits can't do infinite functions.

Therefore, that's already one thing that
we couldn't do before.

So now we're going to show
that anything we can do with a.

NAND circuit, we can also
do with finite state automata.

And the way that we're going to do that...

So I'm not actually going
to show directly how I can

convert any circuit into
a finite state automaton.

Instead, what I'm going to do is,
since we knew that NAND circuits were able

to compute any finite function,
If I can show that finite state automata

can compute any
finite function, then that

means that I can do
anything a circuit could do.

Question.

So that relationship, we call that
incomparable.

So two models of
computing are incomparable if

neither is strictly more
powerful than the other.

If they're non-equivalent and neither is
strictly more powerful than the other.

That is, there's some things this can do
that the other one can't, and there are

some things this can do that the other one
can't.

So we call that incomparable.

We're not going to talk about
any models of computing

that are incomparable
this semester, unfortunately.

So in order to show that finite state
automata are more powerful than NAND

circuits, we're going to show that we can
compute any finite function.

Let's kind of reflect back
about how it is that we

could do any finite
function with a NAND circuit.

So we have this proof that we
did a while back where we said

we can do any finite function
at all with a NAND circuit.

The summary of the idea for how we did
that was if I sort of manually

pre-computed all of the input-output pairs
for that finite function.

There's only finitely
many inputs, so if you

give me long enough,
I can do it eventually.

Then we can put all those input-output
pairs in one big lookup table,

so that when you give me the actual input
you want to know the answer for,

I can just do a lookup in that big table I
created.

So that was the idea for how we did that
with NAND circuits.

This was the example that we looked at.

Here is that table that I pre-computed of
all the input-output pairs.

Here is me building
that table where I said for

each input there is the
output that goes with it.

And then when you give me the input that
you actually care about, then we just do

one big lookup in that table for that
input to give the right answer.

And we're going to see that we can do
something very similar with finite state

automata in order to do any finite
function that we might care about.

Just like before, we're going to manually
pre-compute all of our input-output pairs.

There's only finitely many of them,
so we can do that.

And then we're going to do a lookup,
but instead of looking this up in a table,

we're basically going to do a lookup in a
tree.

Essentially, I'm going
to have a state for

every single possible
input that I could see.

And then once I figure out which ones are
final states versus non-final states,

then what we can do is we're
going to do some traversal through

this tree that we build to
navigate to the right answer.

So let's look at an example of what I mean
here.

So here is that same function from before.

So what I'm going to do
is, just like before, I'm going

to sort of pre-compute
all of the input-output pairs.

And then what I can do
is, I'm going to say, I'm

going to have one state
for every possible input.

So in this case, I have
these eight states here,

one for each of those
eight possible inputs.

And then by looking in my table,
I can determine which of these states

should be final states and which of these
states should be non-final states by

saying anything that had a one as its output
should be a final state in that machine.

So now once I've done this, all I have to
do is say, When you give me some input,

I want to make sure that the transitions
you're going to take inside this finite

state automaton are going to get you to
what the output should be there.

So for instance, if my input was 1,
0, 0, then the path this finite state

automaton is going to take is it's going
to transition right on a 1, left on a 0,

left on a 0, so we return 1 because that
was a final state.

If I had 1, 1, 0, then we would go right
on the 1, right on the 1, left on the 0.

So in this case, we return 0 because that
was not a final state that we ended in.

And then I have some extra states in here
because we have to be able to make a path

to these states that represent our
possible outputs.

And then if my input string was too long,
then we want to go into this trash state

down here because we didn't want to do
anything.

So any finite function you give me,
I'm going to be able to have this binary

tree-like thing in order to navigate to
what the answer ought to be.

So we can do any finite function with
finite state automata.

Questions?

Yeah.

So for a finite state automaton,
we need to make sure, because they have

this loop business to
them, where the longer

the string is, the more
transitions you take.

This finite state automaton
is going to be able to

sort of take as its input
a string of any length.

We only wanted to return 1 for strings
that were of length 3.

So for strings that were longer, we had
that trash state that was a non-final state.

So now we already know this is a strictly
more powerful model of computing,

so we've made progress in the world of
computer science.

We've made progress in the world of
computer science.