Today's topic is closure properties for
the regular languages. We should recall
that a closure property is a certain
operation on languages that says, when the
arguments are languages in the class, then
so is the result. You can see on the title
slide the list of closure properties for
the regular languages that we are going to
discuss. Our first closure property will
be Union. That is if L and M are regular
languages, so is L Union M. To prove this
fact we use the regular expressions, say
RNS, who's languages are L and M,
respectively. We know L and M have regular
expressions because they're assumed to be
regular languages. Then R+S is also a
regular expression, and we know its
language is the union of L and M. The same
idea works for concatenation and closure.
Remember to draw parentheses around R and
S if they are needed, like this. For
example, if R is zero+1, and S is zero.
And you need to write the expression with
parentheses around the zero+1. Otherwise,
you'll get the wrong language. You don't
need the parentheses around the zero.
Regular languages are also closed under
intersection. For intersection we can't
use regular expressions very easily, but
the DFA is perfect for proving closure
under intersection. So we take DFAs A and
B for the two languages whose intersection
we want. And we construct the product
automaton. The final states in the product
are those states that are final in both of
the given [inaudible]. Thus, the product
accepts an input string if and only if
both of the original [inaudible] do. And
that's exactly what we want for
intersecting the languages. Here's an
example based on the same product
automaton we used last time. The only
final state in the product is BC. That's
this, of course. Because B and C are the
only final states of their automata. B and
C are there. Here's an example of how
closure properties prove useful. Okay,
remember we proved, using the pumping
[inaudible], that L1, the set of strings
of 0s followed by an equal number of 1s,
is not a regular language. L two. The set
of all strings with an equal number of
zero as in one. Isn't regular either.
However, supposed l two were in fact
regular. Then since regular languages are
close under intersection. The intersection
of l two with the language of the regular
expression zero star one star will also be
regular. Now the language of zero star one
star are is all strings with any number of
zero is followed by any number of one. But
what is the intersection of [inaudible]
this language. Is [inaudible] one. Because
[inaudible] force is the number of zero
and one is to be equaled. While the
language of zero star one star, ifs for
all 0s to precede all the 1s. Set
differences in other operation under which
languages are closed. The difference of
languages l and m, written l minus m, is
the set of strings in l that are not in m.
For the proof of closure under difference
start with the [inaudible] A and B for
languages L and M respectively. Construct
C, the product automaton for A and B. Make
the final states of C be the pairs where
the state from A is final and the state
from B is not. Then C accepts an input
string from W if and only if A accepts W
but B does not. That W is in the
difference of their languages. Here's our
favorite Autotonic end. This time BD is
the only final state. Because B is the
only final state of the orange atomaton
and D is the only non-final state of the
purple atomaton. Notice that the final
state BD is not reachable from the star at
stake. So this version of the product,
[inaudible] the empty language. That's
exactly as it should be. Because the first
[inaudible], the orange one accepts the
subset of what the second [inaudible]. The
purple one accepts. That is the first
[inaudible] accepts all strings that end
in the odd number of ones. The second
accept all strings that end with at least
one, one plus the empty string. Okay,
let's start from here. The compliment of a
language is defined with respect to some
alphabet sigma. Sigma has to include all
the symbols from the alphabet or the
language L. But may also include other
symbols that don't appear in L. Then the
compliment of L is all strings and sigma
star that are not in L. Since sigma star
is surely a regular language and we know
that regular languages are closed in the
complementation we immediately know that
the compliment of any regular language is
also regular. Now we should look at the
operation on reverse side. Recall one of
our earliest examples of a regular
language is was the language of binary
strings. That when interpreted as integers
and binary were divisible by 23. We
commented then that the language of
[inaudible] strings that when reversed
would be divisible by 23. Was also a
regular language. We also said that
constructing a [inaudible] for that
language is tricky. So here's the tricky
construction. Which really isn't so tricky
now that we have mechanisms like regular
expressions to work with. First, the
notation we use for reversal is
superscript R. That is L super R means the
reversal of language L. This language
consists of the reversals of all the
strings in L, here's a simple example. L
has three strings. Zero, 0-1, and 1-0,
okay? And L reversed is the reversal of
each of these strings. Zero reversed is
still zero, while 0-1 reversed is 1-0, and
1-0-0 reversed is 0-0-1. So L reversed
consists of 0-1-0 and 0-0-1. To begin the
proof that regular languages are closed
under reversal. We start with a regular
expression for a regular language L. We'll
show by an induction on the number of
operators in the regular expression that
there is a regular expression for the
reverse of L. The basis is expressions
that are either single symbols, the empty
string, or the empty set. These are the
only expressions with zero occurrences of
operators. In all these cases, the
expression doesn't change. That is, the
reversal of a string of length one is the
same string. The reversal of the empty
string is still the empty string. And if
you reverse all strings in the empty set,
the set is still empty. The induction
consists of the three operators for
regular expressions. For union, it is
easy. You just reverse the expressions for
the two parts of the union. [inaudible] is
a little trickier. To reverse the string
WX, where X, W comes from F, say, and X
comes from G. You need to reverse W and
reverse X. But then you need to flip the
order of the reverse strings. That is X
reversed comes before W reversed. For
example, if W is, 011, that's W, and X is
01. Then, okay, the W reversed is one, one
zero and X reversed is X0 but the x has to
come first so the reverse of 001101 is in
fact 10110. And for the star, we reverse
the expression F that is starred. That is
this guy, here. So, it now produces the
reverses of all the strings that F
produces. We then star the reversed
expression to get concatenations of any
number of the reverse strings in any
order. Let's reverse this regular
expression. It's language is all strings
of zeros and ones, such that the first bit
never again appears. That is, the strings
are either a zero followed by any number
of ones, that's this part. Or one followed
by a number of zeroes. That's that. The
outermost operator of this expression is
the plus. And the way we reverse a sum of
two expressions is to reverse each
expression separately. That is, the
reverse of this whole expression is the
reverse of the two parts. Separately. Now
let's look at one of the expressions
01-star. We have, let's look at this. We
have to reverse it. So the way we reverse
a concatenation is to reverse each of the
component expressions and put them in
reverse order. So zero one star, it's
reverse is one star reversed followed by
zero reversed. The other expression. One,
zero star which must be reversed is
handled the same way. It's zero star and
we have to reverse that followed by one
which we must reverse. The basis rule
tells us that the reversal of zero is zero
and the reversal of one is one. That is
the reversal of this zero is just that
zero and the reversal of one is just that
one. Also, the reversal of one star, Is
the star of the reversal of one. That's
that. And similarly the reversal of zero
star is star of zero reversed. Finally.
The reversal of one again, that's this,
is. Just one so we get one star zero and
the reversal of zero again is just zero
and we get that now we have no reversals
left and we are done. The resulting
expression is like you would expect, it's
language like the binary strings with the
last symbol does not appear elsewhere.
Metamorphosis are transformations on
symbols that replace each symbol by a
string that may be empty another symbol on
a long string. When a given homomorphism
is applied to all the string of a regular
language, the result is a regular
language, as we shall see. Here's an
example of a homomorphism, one that we
shall use repeatedly in the discussion.
This homomorphism H replaces every zero by
the string AB, and replaces every one by
the empty string. You apply any
homomorphism to a string by applying the
homomorphism to every symbol of the string
in order and concatenating the results.
For example, if we apply our homomorphism
H to the string 01010. Each of the 0's
gets replaced by ab, and the 1's
effectively disappear. Because they are
replaced by the empty string. That is this
zero becomes that AB. This zero becomes
that AB. That zero becomes that AB. And
the ones that are replaced by epsilons
that sort of go in the middle there but
you don't see them of course because they
are empty. Thus, each of 01010 is ABABAB.
We claim that if you take a regular
language L and apply a homomorphism H then
the result is also a regular language.
Note that the result of applying H to the
language L is the result of strings that
you get by applying H to all strings in L.
I'm not going to give you a formal proof,
but the big idea is that you start with a
regular expression for L, and you apply H
to every symbol in that regular
expression. The result will be a regular
expression for L. Here's a simple example.
H is the homomorphism we've been using as
an example right along. L is also a
language who's regular expression is E
which we saw before in connection with
reversal. We compute an expression. For H
or L by replacing each occurrence of zero
in E by AB and each occurrence of one by
the, the empty string. The resulting
expression is this one. Okay, that is this
zero got replaced by AB. >> This one got
replaced by the empty string. That one got
replaced by the empty string. And the Zero
got replaced by AD. >> By the way here is
a good example of where you have to
introduce parenthesis since 0-star does
not need parenthesis but AD star, where if
I just wrote this.... [noise] would be
wrongly interpreted by an A followed by a.
Any number of b's. Rather what we mean is
any number of unit. A b's. We can simplify
this expression considerably. First
[inaudible] star is any number of empty
strings. So we can replace a b [inaudible]
star. That's this by just ab [inaudible].
Remember that the empty string is the
identity under [inaudible]. So we can
remove the [inaudible] to give it just. Ab
plus AB star. Cuz these guys go away. >>
Leaving us just that. >> Hm. >> But, the
language of ab is just one occurrence of
ab. While the language of AB star is any
number of occurrences of AB, including
exactly one concurrence. Thus, we can just
drop the term AB. Here, and we are left
with just a b star. That's the simplified
expression. We can also define the inverse
homomorphism of a language or a string. >>
We do note inverse homeomorphisms by a
super script minus one. That's this
notation. >> Yeah. The result of applying
the inverse of the homomorphism H to a
language L is the set of strings W. Such
as that when you apply H in the forward
direction to W, you get a string in L. So,
here is the language L. These are all the
strings in the language L, okay? And H,
I-, will be represented by a downward
motion. So any string that goes anywhere
in L. When you apply H, these are all an H
inverse of L. And any string that misses L
when you apply H, that's not an H inverse
of L. Here's an example. Let H be the
homomorphism of our running example. L is
the language with two strings, ABAB, and
BABA. That's that right there. Then aging
[inaudible] is the language of strings
that have two zeros and any number of ones
interspersed. Here's a regular expression
for this language. To see why, let's look
at the two strings in L. Abab, and BABA. A
string like 1101101 maps to ABAB. The 1s
disappear as they go to empty string. And
third zero goes to that AB. The second
zero goes to that AB. But nothing can go
to BABA because a zero would cover, has to
cover that AB in the middle. That's the
only way you can map a zero. Now you've
got to be able to map something to the B,
but the only way you can do that is if you
have a zero, but that would then map to
AB. And similarly, this A, there's no way
to map to that A without mapping to
another B which doesn't exist. While for
forward homomorphism, the regular
expression representation was dandy. To
show that the inverse homomorphism of a
regular language is regular, is best done
with DFAs, okay. Start with the DFA, A,
for L, and construct a DFAB for H inverse
of L. B has almost everything the same as
A, the same state, same start state, the
same final state. The input alphabet for B
is the appropriate input alphabet, that is
the set of symbols to which the
homeomorphism H applies. We then fix up
the transition function for B to reflect
both the new set of input symbols and the
effect on those symbols of the
homeomorphism. Suppose B is in state Q.
And the input symbol is A we apply H to A
and we see where the automaton capital A
would go on that sequence of inputs H of
A. That is doubt the B of Q and A. Is
Delta A, that is the, transition function
for the automaton A, starting to stay Q,
but reading. Sequence H of A. Note that H
of A could be the empty string or some
long string of symbols, so this is really
the extended delta, but that's okay. We
know what that is. Here's an example of
[inaudible]. And we'll use the same
[inaudible] in playing with all along.
Since h of one is the empty string. Each
state of the [inaudible] for the inverse
[inaudible] will transition to itself on
one. That's what these transitions are for
example. Are suggesting. For transitions
on zero we need to figure out where the
original [inaudible] goes on a d. For
example starting on [inaudible] a. And
following the path labeled AB. You wind up
in state C. That explains why. And the
transition from A on zero goes to C.
Similarly starting at B and following the
path labeled AB. It's that, you also get
to see and the same thing is true if you
start from C, A and then B. We're not
going to do the complete proof that
regular language is closed under inverse
homomorphism. The heart of the proof is an
induction on the length of W that W takes
atomaton B from the starred state to state
P if and only if the string H of W takes
atomaton A from the starred state to the
same state P. That's this equation. Now B
accepts W and A accepts H of W if and only
if B is a final state. That is, W is in
the language which of B if and only if H
of W is in the language of A, which is the
same thing as saying B accepts each
inverse of the language of A.