---
Video Title: Proving FSAs are as Powerful as Regular Expressions (Part 2: Bases, Union)
Description: Theory of Computation
https://uvatoc.github.io/week7

14.4: Proving FSAs are as Powerful as Regular Expressions
Part 2: Base Cases, Union

Nathan Brunelle and David Evans
University of Virginia
---

So to start with, let's
show that we can build

a finite state automaton
for the empty string.

Do that with your neighbors.

Build me a finite state automaton for the
language of just the empty string.

In the back.

So here we have the start state,
which is also a final state.

That is this first one here.

And then on anything
in the alphabet, we are

going to transition to
maybe some trash state.

And then the trash state transitions to
itself on anything in the alphabet.

So the only way that this
machine can return one

for anything is when we
don't take any transitions.

And the empty string is the only string
that doesn't take any transitions.

Okay, so we can do the empty string.

Any regular expression that is just the
empty string, we can certainly now make a

finite state automaton for that regular
expression.

We have one case down.

Let's do more cases.

Show that if I have a regular expression
that is just a literal character,

show that I can build a finite state
automaton for that regular expression.

Do that with your neighbors.

I'm going to call the literal character x,
just for clarity.

Yeah, go ahead.

So this is saying that we start in the
start state.

If I get the character I was looking for,
then you go to that final state.

If I got anything else from the start
state, this is saying if the character I

got was anything from
my alphabet, except for

whatever x was, then
we're gonna go to trash.

And once I was in
that final state, if I got

anything else, and I
was gonna go to trash.

So the only string which will
cause this automaton to end in

its final state is going to be
just the string containing x.

So no matter what literal
character we had, we

can build a finite state
automaton for that.

So we kind of have our base cases.

These are sort of our two base cases for
this proof-by-induction that we're doing.

By the way, I don't think I ever mentioned
what kind of induction this was.

This is typically called structural
induction.

The idea behind that phrase, structural
induction, is that we're saying that the

thing that we're building has some sort of
structure to it.

And you build upon this structure using
certain rules, and you're showing that you

can build anything because you can just
use those rules, basically.

So you just show since you
can do any of the rules, that

means you can do anything
that you could eventually build.

You have a question?

Yeah, so we're sort of going
to be able to allude to them

in some sort of abstract
way, if that's what you mean.

We can just sort of say, invoke the
literal character thing here, for instance.

Kind of like what we did with syntactic
sugar.

You can think of this
as building up some

finite state automata
syntactic sugar as well.

Okay, we've shown that if I have a really,
really simple regular expression,

I can convert it into a finite state
automaton.

Now I'm going to show that if I have two
simple regular expressions, which I can

represent with finite state automata,
then I can build a new finite state

automaton to represent the alternation of
those two, or the union of those two.

So in order to do this, basically what
this question is asking is, is

computability with finite state automata
closed under union?

That is, if I have two languages,
let's say language one and language two,

and I knew that both of those two
languages could be computed with a finite

state automaton, I want to
know, is the union of those two

also going to be computable
with a finite state automaton?

So when we looked at the definition of
alternation up here, when we do the

alternation of two regular
expressions, that'll match

strings that match at
least one of the two parts.

So it says we can match the first part or
the second part.

In other words, the set of strings that
will match is the set of strings that

match the first one, union the set of
strings that match the second one.

That's why we called this union.

So if I can show that computability by
finite state automata is closed under

union, then that means that I can take two
finite state automata representing regular

expressions and create a
new finite state automaton

representing the union of
those two regular expressions.

Doing this is actually somewhat tricky.

Because we've kind of got two machines.

I've got two automata that I have to deal
with.

Let's say M1 is whatever is the finite
state automaton that computes language one.

And M2 is whatever finite state automaton
computes language two.

If I'm trying to create some
new finite state automaton,

let's call it M subunion
or something like that.

If I'm trying to build some new finite
state automaton that's going to compute

the union of those two languages,
This finite state automaton needs to

return 1 for any string that m1 or m2
returns 1 on.

That's what this machine is going to need
to do.

It's going to need to take some input
string, and it's going to return 1 or 0,

return true or false for that input
string, whatever it is.

And we need to design this
mUnion in such a way that it's

going to return 1 whenever
either m1 or m2 returned 1.

It's going to return 0 whenever both of
them return 0.

So it needs to somehow play the role of
both of these machines.

Whatever it's doing, it needs to be able
to play the role of two machines.

But our model of execution
for finite state automaton

said that we can read
the input how many times?

This mUnion that's going to be computing
the union of those two languages,

it needs to be able to, by reading the
input just once, figure out how both of

these other two machines are going to
answer.

So that's the challenge here.

We need to build this new machine mUnion
that is going to end in a final state,

where for some
string it'll end in a final

state whenever either of
these two machines did.

It will end in a non-final state when both
of these two machines did.

And it needs to be able to answer that
question by reading the input just one time.

So this is the challenge.

Do we understand why, if we can do this,
we can compute union?

So the way that we're going to do this...

So if you'll recall from last class,
we had this example where I said,

here's a finite state automaton for AND,
can we make one for NAND?

And the way we did that is we basically
said, well, AND is the complement of NAND.

So AND and NAND are complements of one
another.

So what we can do is we can just say,
if I have some machine for AND,

I can build a machine for
NAND by just saying, I want all

of NAND's final states to be
the non-final ones from AND.

We can sort of apply this idea to, in
general, doing the complement of languages.

Or we could say, if I've got some finite
state automaton, let's call it M,

that computes the language
L, then this finite state

automaton is going to compute
the language L complement.

Where this finite state automaton is
exactly like the one we saw before.

It's got the same states, the same transitions,
the same start state, and so forth.

The only thing that changed
was which states were

final, which is the opposite
states that we had before.

So in general, what this is saying is that
whenever I can compute some language L I

can compute that language complement with
a different finite state automaton,

guaranteed.

And the reason I know that I can do this
is because whatever finite state automaton

it was that computed
L, I could use it to build

a finite state automaton
for L complement.

So by manipulating that finite state
automaton that I assumed exists,

I could build this new finite state
automaton for L complement by saying,

just do the same thing, but invert the
roles of the states.

So the final ones are non-final,
the non-final ones are final.

So that says that whenever
a finite state automaton

exists for L, there also
exists one for L complement.

And I know that because I can build one
using the one that L had.

This is in general how we
go about showing the closures

for this computability
with finite state automata.

As we say, assuming that we start out with
things with finite state automata.

If we wanted to do this operation on the
language, we can manipulate those finite

state automata in this parallel way in
order to guarantee a finite state

automaton exists for the resulting
language.

So here we said we have the complement
operation we want to do on languages.

This inverse the final state's operation
does the same thing to the automata,

basically, Bie talvez, as complement did
to the languages.

So, our general strategy for computing
union, then, is we are going to say assume

that I have finite state automata for
language 1 and language 2.

Let's call them M1 and M2.

I want to know, whenever there was a
finite state automaton for language 1 and

language 2, was there
also going to be a finite

state automaton for
language 1 union language 2?

Provided one exists, I'm going to end up
calling it m sub union.

So our idea is we want to build this
finite state automaton that can sort of

play the role of both m1 and m2 while
reading the input sort of simultaneously.

So our idea is that this
one finite state automaton is

going to simulate both of
these other two at the same time.

So if I can build one finite state
automaton that can sort of do the same

thing that two might do at the same time,
then that's going to be what gives us now

one finite state automaton for the union
of those two languages.

So let's look at an example of what it is
that we're trying to do here.

So let's say that I wanted
to compute the union

of this AND language
with the XOR language.

I want to compute the union of AND with
XOR.

First of all, who can describe what the
resulting language is?

It's the result of the union.

What things are in the union?

Yeah, so all strings that have only ones
in them.

Or they've got some zeros, but there's an
odd number of ones.

These are two automata for those
languages.

This left-hand side automaton.

This is an automaton for AND.

This is one for XOR.

I want to be able to do the union of this.

And in order to do the union, I want to
have kind of one super automaton that can

do the same thing as both of these other
two.

So for instance, who can give me some string
that they want to put on this automaton?

Any string at all?

1, 0, 0, 1.

Okay.

I'm going to sort of step
through the idea for what

we'd like this super automaton
to do using this string.

Okay, so the super
automaton, it's trying to do

whatever both machines
did as the one automaton.

So that means that instead of being in
just, say, one state at a time,

it's going to be in two states at a time.

One state from the AND machine,
one state from the XOR machine.

Its current state is going
to be which state the AND

machine is in, and which
state the XOR machine is in.

Where are we when we start?

Before we read any characters,
where are we when we start?

We're in start in AND, and even in XOR.

So this super machine, whatever it's going
to do, its start state is going to be

representing AND being in start and XOR
being in even.

The next thing we're going to do is we're
going to read a one from the input.

Where is AND going to be when we read that
one?

Yeah, so AND is going to be in no zeros.

Where is XOR going to be?

Yeah, XOR is going to be in odd.

So now we've read that one.

Next we're going to read a zero.

What happens after we read that zero?

Where is AND going to be?

Yes, we're going to be in some zeros
because we were in no zeros before.

We got a zero.

So we're going to take that transition up
to some zeros and and.

Where is XOR going to be?

Yes, stays the same.

So XOR is going to stay in odd because we
were in odd.

We got a zero.

So we took that self loop to end up at
zero again.

So now we've read that and we're going to
get a zero.

Where is and going to be on that zero?

Some zeros still.

Where is XOR going to be on that zero?

Still odd.

And so we've read that, and now we're
going to do that final one.

So on that one, where is AND going to go?

Some zeros.

Where is XOR going to go?

That's going to go to even.

So we end up in some zeros as well as
even.

So should we return one or should we
return zero?

Both of them were non-final, so we return
zero, which is what we wanted to do.

So this is the behavior that we want this
union machine to have.

To be able to sort of do
what both machines are doing

sort of in lockstep on
that same input question.

That's correct.

If exactly one was in a final state,
we'd want to return one here.

If both of them were in final states,
we'd also want to return one.

We want to take one input
character at a time and

sort of transition in both
machines in lockstep.

That's what we're going to want this union
machine to do.

So we're going to build a union machine
that's going to behave in that way.

Where the way we're going
to do that is we can take this

machine and this machine
is going to have one state.

So this union machine will
have one state to represent

every possible pair of states
in the original machines.

So each possible pair of states in those
original machines, we're going to

represent as a single state in this
combined machine.

So that by transitioning
among these super states, we're

kind of simulating working in
both machines simultaneously.

If we look at our AND
machine and our XOR machine,

this is going to be our
union machine over here.

Where in this case, we end up with six
states in my union machine because I

wanted every possible pair of states from
AND and XOR.

There were three in AND, two in XOR.

So the product of those is the number of
ordered pairs we could have.

So we end up with six states over here.

So now each of these
states is representing

being in some pair of
the original two states.

Which one should be the start state?

Yeah, so start and even, that's the one
that should be the start state.

Because that was the pair of start states
from the original machines.

If I'm in start even and I get a zero,
where should I go?

So where does the AND machine go on a
zero?

So the AND machine on a zero goes to some
zeros.

So that means I need to be going to one of
these two states for sure.

To figure out which of
those two states I want to

go to, I want to figure out
where XOR goes on zero.

Which is back to even.

So on a zero, start even goes to some
zeros even.

Where does start even go on a one?

So it goes to no zeros odd.

So on a one, start even goes to no zeros
odd.

If we're in some zeros even, where do we
go on a zero?

So some zeros and even.

On a zero, some zeros goes back to some
zeros.

Even goes back to even.

So some zeros even goes back to some zeros
even.

On a one, where does some zeros even go?

So some zeros even goes to some zeros odd
on a one.

And we can repeat this for kind of all of
these pairs.

Which ones are final states?

Yeah, so anything that
had either or at least one

of no zeros or odd is
going to be a final state.

Yeah, or start.

No zeros, odd or start.

So start even, that has start in it.

So that's a final state.

Start odd, that had start in it.

So it's a final state.

It also had odd in it, which would be
enough to make it a final state.

Some zeros even is not a
final state because Because

neither some zeros nor
even were final states.

Some zeros odd, odd is a final state,
so this one should be a final state.

No zeros even, no zeros is a final state,
so this one should be a final state.

And then no zeros
odd, both are final states,

so we want this one
to be a final state.

Questions about this?

Yeah, in the back.

No, you would not.

So if you want to see it completed,
there it is completed.

Notice there is no possible way to use
this start odd state up here.

We can still have it in the automaton if
we can't reach it.

It doesn't harm anything.

It's certainly unnecessary,
but it's not actively harmful

to our automaton to just
have it floating around there.

It's even fine if we make it a final
state.

We can never get to
that final state in order to

return one for some
string that took us there.

But that doesn't mean it can't be a final
state.

It just is useless.

Yes?

Yeah, I got lazy and sort
of gave up just to make

it clear that we couldn't
actually get there.

To make this actually properly satisfy the
definition of a finite state automaton,

you would have to have the outgoing
transitions from that state, but there

aren't going to be any
incoming transitions to

that state because it's
impossible to get there.

That is a very good point.

Okay, so this, by the way, is typically
called the cross product construction.

The reason it's called the cross product
construction is because in the machine we

created, the states were pairs of the
original state.

So our state set over here is the cross
product of the state sets over here,

or the Cartesian product, if you prefer
that terminology.

So we typically call this the cross
product construction for automata,

and it essentially allows
you to have one automaton

that does the transitions
for two machines at once.

Or you could do triples
and do it for three machines

or quadruples and do it for
four machines and so forth.

So in general, if you
want to see this in super

hard to read notation,
because why wouldn't you?

If I have this machine one that is defined
as such, where I've got my states,

I've got my alphabet, I've got my
transitions, I've got my start state,

and I have my finals.

And then I have the same thing for this
machine two over here.

I can build this union
machine by saying my state

set is ordered pairs of
the original state sets.

My alphabet is the same as what the other
alphabets had.

I've got some sort of special transition
function that I'm going to talk about next.

My start state is the pair of start states
from the original machines.

And then my final states are
defined down here, which is any

state where one of the two
things in the pair was a final state.

And how does our transition function work?

So if I have some pair of states,
q1, q2, and I want to transition on some

character, my next state should be
transition using the first function on the

first state, transition using the second
function on the second state.

So this is super formally with notation
what cross product is doing.

If you sort of understand
what this is doing

less formally, then
you're totally fine on that.

But that's what it looks like if you want
to do it purely with notation.

Yeah.

Yeah, as long as long as you're
consistent.

In this case, the order does not matter.

I might... so the cross product
construction, we can... we can actually do

other operations, for instance,
intersection, using this... using the same

technique of this cross product
construction.

For different operations I might want to
do, the order might matter for those.

For union, it does not.

Question.

Typically, we just sort of say the
alphabets are the same.

We kind of say, we pick our
alphabet in advance and then we

start talking about some
languages, is usually what they do.

If they're different, then you
would say that the alphabet

for the union machine is
the union of the alphabets.

And you would end up with... it would
be... weird things would happen.

So we're just always going to assume the
alphabets are the same.

How would this change if I wanted to do
intersection?

If I wanted a machine for intersection,
how would... how would this... this

this construction change?

Yeah, go ahead.

Yeah, so for union, we said that we wanted
to... to return one, or we wanted our

final states to be those where either
state in the pair was a final state.

Because we said we wanted to return one
whenever either machine returned one.

If we did intersection,
then we only want to

return one when both
machines returned one.

So our only final state, if we wanted to
do intersection, or our only final states,

plural, would be this one and then our
nonsense one.

So if we wanted to do intersection,
those two would be our final states.

Because those are the only ones where both
states in the pair were final states.

So this cross product construction is
generally useful whenever you want to sort

of have one machine that plays the role of
two.

So union is one case that this might be
useful.

Intersection is another.

Other things that you could do, in fact,
this might make a good homework problem.

I'll tease it for you then.

Is if I wanted to do language one minus
language two.

That's another situation
where it might make

sense to use a cross
product construction.