Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 59 ยท Regular Expressions and Languages

Closure Properties and Decision Properties of Regular Languages

Learn which operations keep a language regular, union, complement, intersection, reversal, homomorphism and more, plus decision algorithms for emptiness and equivalence.

A class of languages is closed under an operation if applying the operation to members of the class always gives another member. For regular languages, closure is both a theorem about the class and a practical tool: if you can build a language from regular ones with these operations, you know it is regular without drawing any automaton. The same facts, used the other way around, help prove that a language is not regular.

The closure properties

Let L1 and L2 be regular languages. Each of the following is regular too, and each has a proof by construction that you have already met.

Operation Why it is regular
Union L1 โˆช L2 Regex L1 + L2, or the product DFA with "or" acceptance
Concatenation L1 L2 Regex L1L2, or ฮต-NFA linking the two machines
Kleene star L1* Regex L1*, or ฮต-NFA with loop-back arrows
Complement ฮฃ* โˆ’ L1 Swap accepting states of a total DFA
Intersection L1 โˆฉ L2 Product DFA with "and" acceptance (or De Morgan: complement of the union of complements)
Difference L1 โˆ’ L2 L1 โˆฉ complement of L2
Reversal L1^R Flip arrows, swap start and accept, determinize
Homomorphism h(L1) Replace each symbol in the regex by its image string
Inverse homomorphism hโปยน(L1) DFA that reads h(a) from the original DFA on each input symbol a
Prefix set Pref(L1) Make every state that can still reach an accepting state accepting
Quotient L1 / a Move the start state: strings w where wa โˆˆ L1
Right quotient L1 / L2 Accept states from which some string of L2 reaches an old accepting state

Regular languages are not closed under infinite unions: the language {a^n b^n} is the union of the infinitely many finite (hence regular) languages {a^n b^n} for n = 0, 1, 2, ..., yet it is not regular.

Homomorphisms and prefixes in code

A homomorphism h maps each symbol to a string, and extends to strings by h(xy) = h(x)h(y). For example h(a) = 01 and h(b) = ฮต. The image of a regular language is regular because you can rewrite its regular expression symbol by symbol.

The code below applies a homomorphism to the language of the expression (ab)*b and checks it against the image of every string in the original language. It also builds the prefix-closure automaton from a DFA.

Python Homomorphism and prefix closure

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For L = {ab}, the prefix language is {ฮต, a, ab}. The dead state x is the only state that cannot reach acceptance, so it is the only one excluded.

Decision properties

Besides closure, the DFA view gives algorithms (called decision procedures) for questions about regular languages. Each of the following is decidable, and all of them run quickly:

  • Membership: is w in L? Run the DFA on w: linear time.
  • Emptiness: is L = โˆ…? Check whether any accepting state is reachable from the start state.
  • Finiteness: is L finite? L is infinite exactly when there is a cycle on some path from the start state to an accepting state (one that is both reachable and able to reach acceptance).
  • Universality: is L = ฮฃ*? Test whether the complement is empty.
  • Equivalence: is L1 = L2? Build the DFA of the symmetric difference L1 ฮ” L2 with the product construction and test emptiness. Or compare the minimal DFAs.
  • Containment: is L1 โІ L2? Test whether L1 โˆ’ L2 is empty.
Python Decision algorithms for DFAs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two machines for "ends in b" are declared equivalent without testing a single string. The check L3 โІ L1 fails because ba contains b but does not end in it. This is the strength of automata: questions about infinitely many strings reduce to finite graph searches. Context-free languages lose most of these properties (see the closure properties of CFLs).

Using closure to prove non-regularity

Suppose L is a language you suspect is not regular. If you can show that applying regular-preserving operations to L gives a language known to be non-regular, you are done. For example, to show L = {w โˆˆ {a, b}* : w has equally many a's and b's} is not regular, intersect it with the regular language a*b*: the result is {a^n b^n}, which is known to be non-regular. If L were regular, the intersection would be too, a contradiction. The next lesson gives the main tool for proving that base case: the pumping lemma.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which operation is NOT guaranteed to keep a language regular?

    Regular languages are closed under finite union only. The non-regular language {a^n b^n} is an infinite union of finite (regular) languages.
  2. 2. How can you decide whether L(M1) = L(M2) for two DFAs?

    L1 = L2 exactly when no string is in one but not the other, i.e., the symmetric difference is empty, and emptiness is a reachability check.
  3. 3. When is the language of a DFA infinite?

    A cycle that is both reachable and able to reach acceptance lets you pump arbitrarily many extra symbols and still accept.
  4. 4. What is the image of {ab} under the homomorphism h(a) = 0, h(b) = ฮต?

    h(ab) = h(a)h(b) = 0 followed by the empty string, which is 0.
  5. 5. Intersecting the language of equal numbers of a's and b's with ab gives which language?

    Strings of the form a^i b^j with i = j are exactly a^n b^n.

Summary

  • Regular languages are closed under union, concatenation, star, complement, intersection, difference, reversal, homomorphism, inverse homomorphism, prefixes and quotients, but not infinite union.
  • Each closure property has a constructive proof using regexes or automata.
  • Membership, emptiness, finiteness, universality, equivalence and containment are all decidable for regular languages.
  • Closure combined with a known non-regular language is a standard way to prove non-regularity.

Next: The Pumping Lemma for Regular Languages