---
Video Title: Finite Automaton for XOR
Description: Theory of Computation
https://uvatoc.github.io/week6

12.4: Finite Automaton for XOR
- Designing an XOR machine
- Example Execution

Nathan Brunelle and David Evans
University of Virginia
---

We're going to look at
an example of one of these

finite state automata for
this infinite XOR function.

The first thing we want to do is we want
to figure out what should our states be

and which one of them should be the start
state.

So when we have an XOR, when we're trying
to compute an XOR, we're just asking this

question, are there an even or an odd
number of ones in this string?

So the two states that we probably want to
have is I want to have maybe one state

that represents or that I've seen an even
number of ones so far.

Or I have another state that says that I
have seen an odd number of ones so far.

Since we have to read our input strings
sort of one character at a time from left

to right without ever going back,
we can imagine how is it that I would

determine whether or not
there were an even number of

ones or an odd number
of ones in that input string.

Maybe if we were to try to do this in some
sort of pseudocode, we could say whenever

I see a one, I might toggle whether or not
I've seen an even or an odd number so far.

So when I see that first
one, then that means

that I'm going to have
seen an odd number of ones.

If I've seen an odd number
so far and I see another

one, then that must mean I
have an even number now.

If I've seen an even number
of ones so far and I see

another one, that must mean
I have an odd number so far.

Whether I've seen an even versus an odd
number of ones should be enough

information for me to sort
of keep around in order to

determine what my answer
ought to be at the very end.

Now that we've identified
what our states ought to be,

let's pick which state it
is that we want to start in.

So before I have seen any inputs,
how many ones have I seen?

Zero.

And is zero odd or even?

Yeah, so zero is an even number.

So in this case, we're
going to say that this

even state is going
to be our start state.

The way we're going to
denote our start state is we kind

of put this empty arrow
coming into it from nowhere.

That says before you've done anything
else, that's the state that you're in.

The next thing we want to
do is figure out which state or

states are the ones that represent
your answer should be one.

So in this case, we
want to return one for this

function whenever we've
seen an odd number of ones.

So this odd state is the one where if we
finally were in that state and if after

reading the whole string,
we had seen an odd number

of ones, then that means
we want to return one.

The way that we denote that that was one
of the final states is we double circle it.

So double circled states, those are the
ones where we return one any other state,

any single circled state.

That means that if we end in that state,
then we should return zero.

As we go through this, as we're
computing on this automaton,

we're going to read one
bit at a time from our input.

And if we're currently in even,
so if our current state is the even state,

we want to switch to odd whenever we see a
one.

So the way that we write
that rule down is we say,

even transitions to odd
when the input is a one.

So it says whenever you're in the even
state, plus you're looking at a one in

your input, then the next state you should
be in is the odd state.

You should update your state to be odd.

Or when you're in even and you see a zero,
you should stay in even.

You haven't changed the
parity of the number of ones

that you've seen, so
you're going to stay in even.

And then we do a similar thing with odd.

If I've seen an odd number of ones and I
get a one as my input, then now I've seen

an even number of ones, so I update my
state.

If I've seen an odd number of ones and I
see a zero, I haven't changed the parity

of the number of ones that I've seen,
so I want it to stay in odd.

So we can run through an example of what
this looks like.

So does somebody just want to call out
some zeros and ones for an input string?

Okay, so this is our input string.

So we're going to see if
the automaton that we drew

here gives us the right
answer for this input string.

So let's sort of walk through what
happens.

So what I want to do is I want to know
kind of what is my current state.

And what state do I start in?

Even.

So that is this even state.

So before I've read any input,
I begin in that even state.

So then the next thing that we're going to
do is we're going to say, well,

I'm in the even state, and I'm going to
process this first character.

So we're going to read
all of the characters in

my string from left to
right, never looking back.

So we can read them once, and we can never
look back.

So if I'm in the even state, and my current
character is a zero, what is my next state?

Yeah, so we're still going to be in even.

So my state is going to be
updated from even to even,

because we're going to sort
of follow this transition here.

So this self-loop is the one that we're
going to take, because that is the one

where we said you move on that transition
whenever you saw a zero.

So we saw a zero, so we take that
self-loop, updating our state to even.

And now we have read this character,
we're never allowed to read it again.

Okay, so now we're in even.

I'm looking at a one as the next
character.

Where do I go?

What's my next state?

Odd.

So this gets updated to odd.

Because we are going to say I'm in even,
and I see a one, so I follow the state,

the transition, where there is a one that
was labeled on there, so I go to odd.

So then the next thing
I'm going to do is I'm

going to say I can never
read that character again.

I'm going to look at a one.

I'm in odd.

When I'm in the odd state and I see a one,
then I move to the even state.

So I'm going to update my state to even.

And I can't look at that character ever
again.

I have a zero, so I'm in even.

I see a zero, so I stay in zero.

So I can't look at that again.

And then I'm going to stay in zero again.

And then I'm going to stay in zero and
even again.

And then finally, I'm going to do that
final transition to odd.

So now we see that we're in odd.

I've read all of the characters.

So I just say, was
I in one of the final

states, or was I in one
of the non-final states?

Since the state that
I'm in, that odd state,

is double-circled,
that means it was final.

So this here tells me that I want to
return one.

So now we can check.

Did the right thing happen?

I had three ones in this string.

So the XOR of that string should be one.