Regular languages are CLOSED under which operations?
AUnion and intersection ONLY
BConcatenation and Kleene star ONLY
Call five: union, inter., concat., complement, star
DOnly concatenation
Answer & Solution
Correct answer: C. all five: union, inter., concat., complement, star
1. Regular languages are closed under MANY operations. The complete list:
- UNION ($A \cup B$): build a new DFA from both using product construction.
- INTERSECTION ($A \cap B$): product DFA with $F = F_A \times F_B$.
- COMPLEMENT ($\overline{A}$): swap accepting and non-accepting states in the DFA.
- CONCATENATION ($A \cdot B$): build NFA using $\varepsilon$-transitions from $A$'s accepting states to $B$'s start.
- KLEENE STAR ($A^*$): NFA with new start state and $\varepsilon$-transitions back.
- REVERSAL, DIFFERENCE, INVERSE HOMOMORPHISM: all closed.
2. So regular languages are an extremely robust class — closed under nearly every interesting operation.
3. Options A, B, D are incomplete subsets.
_Source: Jeff Erickson, "Models of Computation", §2.9 (Closure properties of regular languages)._
Keep practising Theory of Computation
Browse all Theory of Computation questions for GATE CSE, or explore more Computer Science topics.
Related questions
Which class of grammars generates ALL recursively enumerable languages?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isContext-free languages are RECOGNISED by which type of machine?A CFG is AMBIGUOUS ifConsider the CFG with rule $S \to aSb \mid \varepsilon$. The language generated is