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

15.3: Proving FSAs are as Powerful as Regular Expressions
Part 3: Concatenation
- Union using Nondeterminism
- Concatenation

Nathan Brunelle and David Evans
University of Virginia
---

So basically, the whole purpose of this
was to show that non-deterministic

machines are equivalent to deterministic
ones.

So anything I conclude about
non-deterministic machines,

that should apply to the
deterministic ones as well.

So that means that if I can show
non-deterministic machines are equivalent

to regular expressions, deterministic
machines will be too.

For these remaining operations that we
could do with regular expressions,

We are going to express
those using non-deterministic

machines instead
of deterministic ones.

To start with, I will redo
Union using non-deterministic

machines to show you why
this was a worthwhile endeavor.

When we used deterministic
machines for Union,

we had to do this
power set construction.

We had to take our two
machines, make some grand

machine where every
state was a pair of states.

Every state represented a pair of states.

In this case, if we are using
non-determinism, for a non-deterministic

machine, we want to have a machine that
will return one, a machine that will

return one, if either of the original
machines returned one.

What we are saying is, if I am starting
out with some sort of string and I want to

know, is one of these two machines going
to return one for this string?

This is kind of like that, which direction
in the fork is my friend's house question.

So which direction should I go?

Should I go to machine
one or machine two in order

to find the one that's
going to return a one?

It's hard for me to know before I start
looking at my string.

So we're just going to say,
non-deterministically try both.

So from our start state, we're going to
make some new transition that doesn't

consume any input
and sort of goes to the

original start states from
the other two machines.

So now what this says is, I'm going to
have kind of one path I'm going on where I

am running my string on the first machine,
and then some different path I'm going on

where I'm running my string through my
second machine.

If either machine
were to return one, then

this non-deterministic
machine returns one.

So we're doing union.

This was way easier.

So this is sort of the superpower that
non-determinism gives you.

You can do way easier things like this.

Why doesn't this work for intersection?

So we could use basically the same cross
product construction that we use for union

in order to do intersection,
just by changing up our

rules for which states were
final states, if you recall.

Why can't I use just this non-deterministic
approach for intersection?

Right.

So basically the issue is that our
definition of non-determinism,

it's just baked into the definition for
what this model of computing looks like.

It says that we return one if any path,
if any state we're in is a final state.

If we wanted to do intersection,
we wanted to say return one if we had a

final state from each machine or something
like that.

That is just not allowed.

We can't require
that as our return one

condition, just using
this model of computing.

That violates the model to say something
like that.

So because the model says always return
one if any state is final, we're not going

to be able to just do intersection using
this approach.

You could still do intersection,
but you'll have to do kind of that cross

product approach that
we talked about last time

to do it, even if you're
talking about NFAs.

So if we wanted to express union using
non-determinism in sort of general terms,

the idea is if I have some machine M1 and
some machine M2, and I want a new machine

that is going to do the union of the
languages of M1 and M2.

I want some new machine that's doing the
union of the languages for M1 and M2.

The way I do that is I introduce
some new start state that

has these epsilon transitions
to the previous start states.

That's all I have to do.

If this cloud, this first cloud just
represents some automaton, this other

cloud represents a different automaton,
I'm just going to introduce a new start

state and then draw
these input-free transitions

from the new start
state to the old ones.

And then the old ones are no longer start
states.

Okay, so now let's talk about
concatenation.

So we talked about how one of the rules
for regular expressions is that if I had

some regular expression R1 and some
regular expression R2, I could concatenate

the first one with the second one to make
some new regular expression.

And basically what this
is saying is this is going to

match any string where we
could break it into two chunks.

The first chunk matching
regular expression one,

the second chunk matching
regular expression two.

So a string matches the concatenated
expression if we can separate it so that

each half or each portion is matched by
each of the original regular expressions.

So this operation that we're doing on the
regular expressions here, this is an

operation that we call language
concatenation.

If R1 matches all the strings in some
language and R2 matches all the strings in

some other language, R1,
R2 matches all the strings

in the concatenation
of those two languages.

We're here, the definition of language
concatenation.

If I have L1 and L2 and I
concatenate them, sometimes

you'll see them just
smush together like that.

Other times we'll put a dot in between
them to represent concatenation.

So that is the set of all strings,
such that I can find a string in L1 and a

string in L2, where the
L1 string concatenated

with the L2 string
gave me that string.

So this is just me describing that
separation idea in the opposite order.

W belongs to L1 concatenated L2,
if I can find An X part that belongs to

language 1, and a Y part that belongs to
language 2, which together make that string.

So for instance, if I had this language is
L1, and this language is L2.

So L1 is empty string, and then 0,
and then 10, and L2 is 0, and then 00.

Then every possible way I can take
something from L1 and concatenate it with

something from L2 gives me a string in
their concatenation.

For instance, I can get 0 because that was
concatenating the empty string with 0.

I can get 00 because that was
concatenating the empty string with 00.

I can also get 00 because that was
concatenating 0 with 0.

There were two different ways for me to
have gotten 00 in the result.

I can also get 100 because that was 10
with 0.

I can get 1000 because that was 10 with
00.

This is almost like a cross product.

It's very similar to a cross product.

The main way it's different from the cross
product is because epsilon paired with

zero would be a different thing from zero
paired with zero in a cross product.

But with concatenation, epsilon
paired with zero zero and zero

paired with zero are different
things in the cross product.

But they both gave me zero zero in the
concatenation.

So this is what language concatenation
means.

So what we'd like to do is figure out if
we have two languages with finite state

automata, can I build some
new finite state automaton

for the concatenation
of those two languages?

That's what we want to ask next,
so that we can see, oh, that thing that we

could do the regular expressions, we could
do that to finite state automata as well.

So we can do this concatenation using our
non-deterministic finite state automata.

So our goal is we want
our automaton to return one

if our input string can be
broken into two chunks.

The first of the two chunks... order
matters here, keep in mind.

The first of the two chunks, M1 should
return one on that.

And for the second of the two,
M2 should return one on that one.

So we want to break it
into two chunks where the

first machine returns
one on the first chunk.

The second machine returns one on the
second chunk.

So, for instance, this was our machine for
AND, this was our machine for XOR,

so if I wanted to do AND concatenated with
XOR, I want to know, can I find for this

input a first chunk that satisfies this
AND machine, such that this AND machine

will return one on that first chunk,
and a second chunk that satisfies XOR.

So, the issue is that if I've got some
sort of string, then as I'm reading this

string, it's hard for me
to tell when the first chunk

ought to stop and the
second chunk ought to begin.

That's challenging for me to do,
because it could be that, like, maybe.

.. yeah, so let's say that I had a
bunch of ONES to start with over here.

With AND, this needs to be something with
only ONES.

If I look at, like,
just the first one, that

is a string that AND
would return one on.

Should I make the rest of the string
something I try for XOR?

Or should I have done something else
instead?

Is the question that we would need to ask.

And until I look at
the rest of the string,

that's going to be hard
for me to determine.

So, saying that first one went with AND,
and then the rest went with XOR.

It could have been that that allowed both
machines to return one.

But maybe it could have instead been that
saying the first two ONES went with AND,

and then the rest went with XOR.

Maybe that was the one that would have
done it.

And the first one didn't actually work.

But the issue is, with our
finite state automata, we're

only allowed to read our input
once, without looking back.

So we can't just try something and then go
back if we were wrong.

So instead, we're going to use this power
of non-determinism to say, it might be

that we should move on to
the second language, or it

might be that I should keep
staying in this first machine.

So maybe I should stay in the first
machine, or maybe I should move on.

I don't know which one's going to take me
to my friend's house.

So let's try both.

So that's what we're going to do here.

So basically our goal is we want to make
sure, in this new machine we're building,

we want to return one for any string that
can take me from the start state in the

first machine, through some path in that
first machine, to a final state in that

machine, to a start state in
the second machine, through

some path to end in a final
state for the second machine.

So to do concatenation, we have to have
some way of doing that.

We go from start in the first machine to a
final in the first machine, to the start

in the second machine, to a final in the
second machine.

We somehow have to
get from start to final in

both machines, each for
one chunk of the string.

So that is our goal.

If we can do that, then we have a machine.

If we can make a machine
that will do that, then we have

a machine for the concatenation
of these two languages.

The way that we're going to achieve that
is we're going to say every single time

I'm in some final state
of the first machine, that's

an opportunity for me to
move on to the second machine.

I have the option at that
point to say, oh, the rest

of the input, that's going to
go on the second machine.

I'm done with the first machine.

I've made that one work.

The rest of the input can go on the second
machine.

But I'm not sure if
it's going to, if this is

the right time to move
to the second machine.

So non-deterministically, I'm also going
to stay in the first machine.

So every single time I'm in a final state
for the first machine, I'm going to have

one of these empty string transitions,
one of these empty transitions,

taking me to the start state in the second
machine.

Every single time I've made it so that the
first machine works out, I'm

non-deterministically saying, let's
continue working in the first machine.

But also, in parallel, do the rest of the
input on the second machine.

And if there was some way for me to make
it to a final state in the second machine

through that procedure, then I had
something in the concatenation.

This machine is no longer going to be a
final state.

The final states in this machine are no
longer going to be final.

The only final states are going to be in
the second machine because I have to get

to the end of the second machine to return
one.

But I knew that I got to a final state in
the first machine because that was the

only way for me to get to the second
machine in this case.

So our idea in general is if we have some
machine one, some machine for the first

language, some machine
for the second language, then

I start in the start state
for the first language.

Every single time I get to a final state
in that first machine, I move

non-deterministically to the start state
of the second machine.

And then the first machine's final states,
I make non-final.

So that is my construction.

Yeah, so that should be the same thing,
but without my terrible handwriting.

Yeah, and non-determinism just sort of
takes care of that for us, actually.

So you do have to make sure you're trying
every possible combination.

So what's going to happen
is every single time I end up in

one of the final states of
the first machine, we branch.

We see a fork in the road.

So I've introduced a fork in the road for
every final state of the first machine.

So no matter when I got there,
how I got there, anything like that,

any time I end up in one of
these final states, I have a

fork in the road, so I'm
going to take both directions.

Where one direction is
going to be stay here, the

other direction is going
to be move over there.

So every single time we enter one of these
states, we branch.

And it could happen many, many times while
we are processing the same string.

So for instance with this one,
with this example, if I just kept getting

ones, if I had a bunch of ones to start
with then, yeah every single time I would

say stay in here, but then also go over
there.

And then stay in here again, but then also
go over there.

For every single one, we're going to have
all these branches.

We're going to have lots and lots of
different branches and lots and lots of

different paths and so forth that we're
doing.

All of those many, many, many different
options are all happening at the same time.

We don't even have to worry about it.

Magic takes care of it for us.

The magic of theory.