closure-properties

1. Regular Languages

Recall that a language that is recognized
by a DFA (or NFA, or RegExp) is called a
regular language

2. Closure Properties

If L1 and L2 are regular languages, then the
following are also regular languages:
L1 ∪ L2
L1 ∘ L2
(concatenation)
L1 ∩ L2
∑* ─ L1 (the complement, L1)
L1 ─ L2
L1R
(the reverse of L1)
How would you go
about proving these?

3. Union and Concatenation

If L1 and L2 are regular languages, then there
are RegExp’s R1 and R2 that recognize them
R1 | R2 is a RegExp that recognizes L1 ∪ L2
R1 R2 is a RegExp that recognizes L1 ∘ L2

4. Intersection

Suppose we have DFAs D1 and D2 for regular
languages L1 and L2
General idea: Construct a new DFA D∩ with
states that are labeled with the Cartesian product
of the states from D1 and D2
If qk and rj are states of D1 and D2 respectively,
then <qk, rj> is in D∩
If both qk and rj are both final states, then <qk, rj>
is a final state of D∩
The start state of D∩ is <q0, r0>

5. Intersection

Transitions now define where we would go next
in both D1 and D2 for a given character
For any character c:
If qk transitions to qj in D1, and
If rm transitions to rn in D2,
Then <qk, rm> transitions to <qj, rn> via c in D∩

6. Intersection

Transitions now define where we would go next
in both D1 and D2 for a given character
For any character c:
If qk transitions to qj in D1, and
If rm transitions to rn in D2,
Then <qk, rm> transitions to <qj, rn> via c in D∩
Note that this same construction works for union, if
we change the final states in the new DFA to be those
pairs where either state in the pair is final

7. Demonstration

Construct DFAs for the languages L1 and L2 where:
L1 = strings in {a, b}* that contain an odd
number of b’s
L2 = strings in {a, b}* that end with ab
Now, use these to construct a DFA for L1 ∩ L2

8. Complement, Difference & Reverse

Complement, Difference & Reverse
Main ideas (try to do them yourself as
exercises):
Complement:
Change the accepting to nonaccepting states, and vice-versa
Difference:
Use the other closure properties and
some basic set theory
Reverse:
Reverse the DFA transitions (but what
about if we have multiple final states?); Also look
at using regular expressions for this

9. Non-Regular Language Example

There are some languages that are not
regular
Example: { an bn | n ∈ N}
Try creating an NFA for this language
to intuitively see why it is not regular
(we will show how to prove it next
week)

10. Quick Quiz: True or False?

1.
If R is a regular language, then R ∪ {anbn} must be
non-regular
2.
If R is a regular language, then R ∩ {anbn} must be
non-regular
3.
If F is a finite language, then it must be regular
4.
(a|b|c)*
If B is an infinite language,
then it must be nonregular
5.
If N is a non-regular language, then N must be nonregular
6.
If N1 and N2 are non-regular languages, then N1 ∪ N2
must be non-regular
7.
If N1 and N2 are non-regular languages, then N1 ∩ N2
must be non-regular