---
Video Title: Warm-Up: Complementing the XOR Language
Description: Theory of Computation
https://uvatoc.github.io/week7

14.1: Warm-Up: Complementing the XOR Language
- Devising a Regular Expression for complement-XOR

Nathan Brunelle and David Evans
University of Virginia
---

A few classes ago, we talked about this
XOR language.

We could talk about the infinite XOR
language, which is going to contain all

strings of zeros and ones, where that
string has an odd number of ones.

What I'd like for you
to do is write a regular

expression for the
complement of that language.

There's a few different notations you
might have seen before for complement.

You could kind of have this exponent of C
for the set.

That is one notation for complement.

Or you could have this over bar thing.

The complement in this case means the set
of all strings containing zero or one,

except for the ones that are in XOR.

Come up with a regular expression for the
complement of this XOR language.

So first of all, who can kind of more
succinctly describe this language,

complement XOR?

What kinds of strings belong to that
language, complement XOR?

Yeah.

Yeah.

Yeah, so this is going to be strings with
an even number of ones.

So every string is going to have some
number of ones in it.

If that number of ones was odd,
that language should be XOR.

It should belong to XOR.

So if we want everything
that doesn't belong to XOR,

we want the ones that had
an even number of ones.

How many agree that this works?

How many think that this breaks for
something?

What do you think it breaks for?

11011.

Okay, so let's try it.

Let's see.

So when we look at 11011, so we want to
figure out, is there some way I can,

first of all, break it into two pieces?

So the first piece matches zero star,
and then the second piece matches that.

So we have a concatenation to figure out,
with this regular expression, if it

matches the string, we need to basically
say, break the string into two pieces so

that we can do the concatenation over
here.

So can we break this string into two
pieces such that the first piece matches

zero star, and the second piece matches
this other thing?

What would the first piece have to be in
order for this to work?

Certainly the only way we're going to have
any hope of doing this is if the first

chunk was the empty
string, because zero star

that says we can have
zero or more zeros.

Since this string started with a one,
the only way for us to have matched zero

star was if we chose to have no zeros at
all.

So the empty string is going to match zero
star, so that must mean that 11011 has to

match the rest, has to match this other
thing.

So the next thing we need to do is figure
out, can I split this up into several

pieces so that every single piece matched
the stuff in the parentheses?

So I can break it into any number of
pieces I would want so that every single

piece matches the stuff in the
parentheses.

Can I do that?

Yeah.

How?

What are my pieces?

Okay, so you'd like to break this into
three pieces.

We're going to have 110 and 11.

Okay, so let's see if we can make 110
match the inside of the parentheses first.

To do that, we need to match the one,
which we're good.

And then we need to match zero star, which
we can pick the empty string for that.

So we're good on that.

And then we need to match the other one.

So we're good.

And then we can choose to pick 10.

So we match that.

So we matched all of the four pieces with
110.

With 11, we're going to match the one.

So we're good.

We have zero zeros, and then we're going to
match the one, and then zero zeros again.

So one one also matches the inside of the
parentheses.

So therefore, this whole string does
indeed match as we wanted.

So I believe that this regular expression
does work.

Some things to notice that I think are
important to see when you're kind of

trying to come up with these regular
expressions.

Here, we said that we wanted an even
number of ones, which meant that I needed

to make sure that I only ever added ones
in pairs.

So if we look at this regular expression,
I add a one here, I add a one here,

and those are both inside the star,
so I can only ever add ones in pairs,

which is how we maintain the fact that we
have, say, an even number of ones in there.

We also need to make
sure that I can have zeros

kind of arbitrarily
intermixed with the ones.

So we can see that maybe
I've got zeros before the ones, I

have zeros between the ones,
I have zeros after the ones.

And since there's stars on those,
I could skip the zeros if I wanted to,

or I could have as many as I would like
instead.

Since I'm only ever producing an even
number of ones, since they're being

generated in pairs, and I can intermix
zeros however I would like, that's what's

going to make this represent the correct
language.

There are other things that could work
here as well.

Is the empty string in this language?

Yes, how does the empty string match the
regular expression?

Who can answer that?

How does the empty string match the
regular expression?

Yeah.

Yeah, so I can match the empty string
because I'm going to say something like,

well, the empty string, I need to break
that into two pieces.

Those two pieces are going to be the empty
string and the empty string.

The empty string concatenated with the
empty string, that's still the empty string.

So that means I can sort of say the first
piece is the empty string, the second

piece is the empty string and then that
matches both of the zero star and the star

on the parentheses because in both
situations I just chose zero copies.

So the question was,
does the empty set have

an infinite number of
empty sets inside it?

The empty set is empty, so it doesn't have
anything inside it at all.

But any number of
unions of the empty set is

going to still just
result in the empty set.

Does that answer your question?

Okay.