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

12.5: Formalizing Finite State Automata

Nathan Brunelle and David Evans
University of Virginia
---

So if we wanted to have a formal
definition, so as a formal definition for

what a finite state automaton looks like,
this is just all of the pieces that we saw.

So we have a finite set of states that we
call Q.

We have some sort of transition function
that takes as input a pair of a state and

a character from the alphabet and produces
some state as output.

So the domain of this transition function
is Q cross sigma, so that is the states

cross the alphabet, and then the output is
a state.

So in this case, there are a finite number
of states, this being a finite state

automaton, there are a finite number of
states.

Our alphabet, we said, is also always
going to be finite.

So this transition function that we call
delta, that is a finite function,

which means we could implement it how,
if we really wanted to?

We could hypothetically create a NAND
circuit to do this.

So if you really, really wanted to
actually implement this in some hardware,

then you could represent the transition
function as a NAND circuit of some kind.

We identify one of the states as being the
initial state, and then some other subset

of states, however many we want,
as the final states.

And then these five things together,
what are my states?

What's my alphabet?

What's my transition function?

What's the initial What are the initial
state?

What are the final states?

Those five things together define the
implementation of that automaton.

This rule that we describe here for an
execution, there's kind of this for loop

where the number of iterations that for
loop is going to go is however many bits

were given as the input, or however many
characters were given as the input.

So this just says, for each character,
you're going to do this thing.

So it's going to do more things if you
give it more characters.

There's no upper bound on the number of
steps this could take.

So the more characters you give it,
the more steps this is going to take,

which is what's allowing it to do infinite
functions, which circuits could not do.

Other questions?

Yes.

So basically his question was,
what sorts of things can this compute?

To just put this in really broad terms.

The fundamental challenge of a finite
state automaton is this finite state thing.

Since you're only allowed to use what
state you're in and what character you're

looking at to determine what state to go
into next, if there was some other piece

of information you wanted to keep around
that you didn't in advance pick as one of

your states, then this isn't going to help
you with that.

Yeah.

We can't have an infinite string of
characters, but there's no limit to how

many characters the input string could
have.

There's no bounds to the length of the
string.

All the strings that we're ever going to
compute are going to be finite.

But for these infinite functions,
there's no limit to how long the strings

could be, which says
the domain is infinite,

which is why we call
that an infinite function.

Not because the inputs
themselves are infinite,

but because the number
of options is infinite.

So this is basically some pseudocode for
the execution, where we have some sort of

variable we could
think of as being our

current state that's
initially the start state.

And then for each bit or each character in
the input, we're going to update the state

to be the result of the
transition function applied

to that state and the next
character in the string.

And then the value we return
is basically whether or not the

state we were in was one of
the final states that we had.

This is how our execution model looks.

This is how our
mission application, and

the archipure, which
is the use of the data.