Home › GATE CSE › computerscience › Theory of Computation › Regular languages are CLOSED under which operati…
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)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?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$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?