Questions: Closure Properties of Regular Languages

Question 1

To prove that regular languages are closed under complement, you take an NFA for language L and swap its accepting and non-accepting states. Does this correctly produce the complement language?

• A. Yes — swapping accept states always computes the complement for any finite automaton
• B. No — this construction only works for a DFA, not an NFA, because an NFA may have multiple paths for the same string, some accepting and some not
• C. No — complement closure requires building an entirely new automaton from scratch using a different algorithm
• D. Yes, but only if the NFA has no epsilon-transitions

Answer: (B)

Complement closure requires a DFA, not an NFA. A DFA processes every string to exactly one state — there is no ambiguity — so swapping accepting and non-accepting states correctly gives the complement. An NFA, however, may have multiple computation paths for the same string: some paths might reach an accepting state while others do not. An NFA accepts if any path accepts. Swapping states on an NFA gives you something that accepts strings for which some path reaches a new 'accepting' state — but that is not the complement of 'no path accepted.' The key insight is that DFA determinism (one state per string) is what makes the state-swap argument valid.

Question 2

You have a regular language L1 of valid email address formats and a regular language L2 of reserved system strings. You want to recognize valid email addresses that are NOT reserved strings. Which closure properties do you need?

• A. Union only — combine both languages and filter the result afterward
• B. Concatenation — append L2 to L1 to exclude those combinations
• C. Complement and intersection: L1 ∩ complement(L2) gives valid addresses that are not reserved strings
• D. Kleene star applied to the difference between L1 and L2

Answer: (C)

Set difference (L1 minus L2) gives strings in L1 that are not in L2, which equals L1 ∩ complement(L2). Since regular languages are closed under both complement and intersection, the result is guaranteed to be regular — still recognizable by a finite automaton, still efficiently decidable. This is closure properties functioning as a construction toolkit: you combine known regular languages using closed operations and know the result stays within the regular class, without needing to build a new DFA from first principles.

Question 3

If L is a regular language recognized by an NFA, you can compute the complement of L by swapping the NFA's accepting and non-accepting states.

• T. True
• F. False

Answer: False

Complement construction requires converting to a DFA first. An NFA accepts a string if any computation path accepts it. After swapping states on an NFA, a string would be 'accepted' if any path reaches a new accept state — but the complement should accept exactly the strings for which all paths rejected. Only a DFA, where every string has exactly one computational path to exactly one state, guarantees that state-swapping correctly computes the complement. The standard procedure is: NFA → DFA (via subset construction) → swap accept states.

Question 4

Closure under intersection can be proved directly from closure under union and complement, without constructing a product automaton.

• T. True
• F. False

Answer: True

By De Morgan's law: L1 ∩ L2 = complement(complement(L1) ∪ complement(L2)). Since regular languages are closed under complement and under union, taking complement, then union, then complement again yields a regular language. This algebraic derivation is valid and avoids the product automaton construction entirely. Both proofs are correct — the De Morgan approach shows how closure properties compose algebraically, while the product automaton is a direct constructive proof that often builds more intuition about what the machine is actually doing.

Question 5

Why do the closure properties of regular languages under union, concatenation, and Kleene star correspond exactly to the three operators in regular expressions?

Model answer: Regular expressions are built from exactly these three operations: union (|), concatenation (juxtaposition), and Kleene star (*). The closure properties — regular languages are closed under all three — are the algebraic guarantee that every regular expression defines a regular language. If any of these operations could produce a non-regular language, regular expressions would not correctly characterize the class of regular languages. Conversely, the Kleene theorem proves that every regular language can be described by a regular expression — and the three closure properties are what make that expressiveness possible. The correspondence is not coincidental: it is the algebraic reason the regular expression formalism is both coherent and complete.

This connection also works as a proof technique. To show that a language is regular, it suffices to show it can be built from known regular languages using union, concatenation, and Kleene star — because closure guarantees each step stays within the regular class. The closure properties are not just facts about automata; they are the bridge between the algebraic formalism and the computational model.