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

16.2: Limitations of Finite State Automata
- Why is there no FSA that can compute infinite majority?

Nathan Brunelle and David Evans
University of Virginia
---

There are things we can do with Python that
we can't do with finite state automata.

For instance, we talked about that
majority function, which took three input

bits and returned one if at least two of
them were ones.

We could generalize majority to take any
number of input bits.

We're just going to say this returns one
if there are strictly more ones than zeros.

So it's not so difficult to generalize
majority for any number of input bits.

Where we just say it returns one if the
strict majority of the input bits were ones.

It's not too difficult to compute majority
in Python.

So we can do this infinite function using
some Python code.

Where we just said for each of the bits in
our input, if that bit was one,

I'm going to add one to the count of the
bits.

And then check if that was greater than
half the total bits.

Even though this is really, really easy to
do in Python, it's pretty basic to do in.

Python, it's going to be absolutely impossible
to do with a finite state automaton.

Let's talk about why.

So let's consider what this majority
function looks like.

So let's say that we've got inputs with
lots and lots and lots of zeros,

lots and lots and lots of ones.

Let's look at some long inputs of this.

And for now, I'm just going to only be
thinking about inputs where I have all of

the zeros occurring before all of the ones
do.

Just to make things a little bit simpler.

If we have 49,999 zeros and 50,000 ones,
then in this case we want to return one.

If we had 50,000 zeros and 50,000 ones,
we wanted to return zero.

Because we didn't have a strict majority
of ones.

They were the same, so that's not a
majority.

If we had 50,000 zeros and 50,001 ones,
then now we want to return one.

Because we have a majority ones.

In our model of computation for finite
state automata, we said that we were

always going to be
reading things one bit at

a time, and we were
never allowed to go back.

Once I had finished reading
all 49,999 of these zeros, I

was never allowed to go back
and look at another zero again.

I'm never going to see another zero for
the rest of my computation.

It's just going to be ones the rest of the
way.

That means that by the time I finish with
these zeros and transition to these ones,

I'm going to need to have some way of
keeping track of how many zeros I had,

so I could kind of
sort of count them off

against the ones as
I'm looking at the ones.

So in order to do this right, in order to
compute this function properly,

I need to be able to keep track of I had
fewer zeros than ones in this case,

because there were 49,999 zeros and 50,000
ones.

And notice I have to answer
something differently in this

situation versus when I had
50,000 zeros and 50,000 ones.

And from this 49,999, I also had to be
able to distinguish when I had that many

zeros versus 49,998, which I
had to distinguish from 49,997,

which I had to distinguish
from 49,996, and so forth.

If I couldn't distinguish between when I
had 49,999 zeros and 50,000 zeros,

then that means that
I must have gotten the

wrong answer in one
of those two situations.

If I couldn't distinguish when I had read
49,999 zeros versus 50,000 zeros before

looking at the same number of ones,
if I couldn't distinguish those two

situations, then I'm going to
get the wrong answer sometimes,

which means I didn't actually
implement my function.

I implemented some other function instead.

So this means, because I need to
distinguish 49,999 from 50,000 and from

one fewer than that and two fewer and
three fewer and so forth, in order to

count that I had 50,000 zeros,
I'm going to need at least 50,000 states.

If I had that, say, this is a state where
I could get to it by 50,000, or by having

50,000 zeros, or by having 49,999 zeros,
if I didn't know which situation brought

me here, then once I transition out of
here to start looking at ones,

I have to get the same answer both times.

But here, the answers were different.

I need to have a different state.

So after I'm done processing the zeros,
I need to be in a different state when

I've read 50,000 of them, compared to when
I've read 49,999 of them.

So this means, if I want to be able to
give the right answer for this string of

49,999, and I want to be able to give the
right answer for this string, where I had

50,000, I would need to have 50,000
states, at least 50,000 states.

If I wanted to then give the
correct answer when I had

50,000 and one zeros, I would
need 50,000 and one states.

If I wanted to give the
right answer for 50,000

and two zeros, I'd need
50,000 and two states.

So basically, the problem here is that
more zeros requires more states.

Which means that if I wanted to make one
finite state automaton that would work no

matter how long the input was,
so no matter how many zeros I would have,

I'm not going to be able to pick a finite
number of states to do that.

There's not going to be any way I could
actually pick a finite number of states.

So that no matter how
many zeros we got as our

input, we're always going
to give the right answer.

Because if I have more
and more zeros in my input,

I'm going to need more
and more and more states.

So in order to do this right, I would need
an infinite number of states.

Automata with infinite number of states
are not finite state automata.

There are going to be things we can't do
with finite state automata.

For instance, majority.

That are simple to do with other models of
computation.

For instance, Python.