Practice free →
HomeGATE CSEcomputerscienceTheory 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)._
Solve this in the app — GATE CSE practice & 24k+ MCQs →
Related questions