EXERCISES
1. Fill in the details of the constructive proof of closure under intersection in
Theorem 4.1.
2. Use the construction in Theorem 4.1 to find nfa's that accept
(a) L ((a + b) a*) ∩ L (baa*).
(b) L (ab*a*) ∩ L (a*b*a).
3. In Example 4.1 we showed closure under difference for regular languages,
but the proof was nonconstructive. Provide a constructive argument for this
result, following the approach used in the argument for intersection in
Theorem 4.1.
4. In the proof of Theorem 4.3, show that h (r) is a regular expression. Then
show that h (r) denotes h (L).
5. Show that the family of regular languages is closed under finite union and
intersection, that is, if L 1 ,L 2 ,…, L n are regular, then
and
are also regular.
1. Fill in the details of the constructive proof of closure under intersection in
Theorem 4.1.
2. Use the construction in Theorem 4.1 to find nfa's that accept
(a) L ((a + b) a*) ∩ L (baa*).
(b) L (ab*a*) ∩ L (a*b*a).
3. In Example 4.1 we showed closure under difference for regular languages,
but the proof was nonconstructive. Provide a constructive argument for this
result, following the approach used in the argument for intersection in
Theorem 4.1.
4. In the proof of Theorem 4.3, show that h (r) is a regular expression. Then
show that h (r) denotes h (L).
5. Show that the family of regular languages is closed under finite union and
intersection, that is, if L 1 ,L 2 ,…, L n are regular, then
and
are also regular.