This page summarizes closure properties for regular languages and how to exploit them.
Recall that a set S is closed under an operation X if the output of X is in S whenever the inputs were in S. So, for example, saying that the regular languages are "closed under union" means that if P and R are regular languages, then so is the union of P and R.
Regular languages are closed under a wide variety of operations.
- Union and intersection
- Pick DFAs recognizing the two languages and use the cross-product construction to build a DFA recognizing their union or intersection. See Sipser Theorem 1.25. Also see Sipser 1.45 for another way to do union.
- Set complement
- Pick a DFA recognizing the language, then swap the accept/non-accept markings on its states.
- String reversal
- Pick an NFA recognizing the language. Create a new final state, with epsilon transitions to it from all the old final states. Then swap the final and start states and reverse all the transition arrows.
- Set difference
- Re-write set difference using a combination of intersection and set complement
- Concatenation and Star
- Pick an NFA recognizing the language and modify it as described in Sipser Theorems 1.47 and 1.49
- Homomorphism
- A homomorphism is a function from strings to strings. What makes it a homomorphism is that its output on a multi-character string is just the concatenation of its outputs on each individual character in the string. Or, equivalently, h(xy) = h(x)h(y) for any strings x and y. If S is a set of strings, then h(S) is {w : w = h(x) for some x in S}.
To show that regular languages are closed under homomorphism, choose an arbitrary regular language L and a homomorphism h. It can be represented using a regular expression R. But then h(R) is a regular expression representing h(L). So h(L) must also be regular.
Notice that regular languages are not closed under the subset/superset relation. For example, 0*1* is regular, but its subset {On1n : n >= 0} is not regular, but its subset {01, 0011, 000111} is regular again.
Once we know that some specific languages are regular, closure properties can be used to quickly show that lots of other languages are also regular. More importantly, if we know that some specific "seed" languages are not regular , we can use closure properties to show that lots of similar languages are also not regular. This is done using a proof by contradiction of the following form:
Suppose that the new language L' is regular.
Use one or more closure properties to show that some seed language L is regular.
But we know (e.g. we showed in class) that L isn't regular. Therefore we have a contradiction. Therefore, L' must not be regular.
For example, let L be {On1n : n >= 0}. We showed that L is not regular, using the pumping lemma. Suppose that L' is {wcx : w and x are strings in {a,b}* and |x|=|w|}. Using closure properties, we can quickly deduce that L' is not regular from the fact that L is regular. Specifically
Suppose that L' is regular. Then let F = L' ∩ a*cb* must be regular because regular languages are closed under intersection.Now, consider the homomorphism h which maps a → 0, b → 1, a → ε. Since regular languages are closed under homomorphism, h(F) must be regular. But h(F) is {On1n : n >= 0}, i.e. L. We showed in class (using the pumping lemma) that L is not regular. So we have a contradiction.
Therefore, we must have been wrong in our assumption that L' was regular.