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.