Home › GATE CSE › computerscience › Theory of Computation › If $L$ is regular and $L'$ is its complement (ov…
If $L$ is regular and $L'$ is its complement (over the same alphabet), then
A$L'$ is also regular (closed under complement)
B$L'$ is never regular
C$L'$ is context-free but not regular
DClosure under complement is undecidable
Answer & Solution
Correct answer: A. $L'$ is also regular (closed under complement)
1. Closure under complement is one of the key properties of regular languages.
2. Construction: take the DFA for $L$. Compute its complement DFA by SWAPPING accepting and non-accepting states (i.e. $F' = Q \setminus F$).
3. This DFA accepts exactly the strings the original rejected — which is the complement language.
4. Note: this construction works for DFAs but NOT directly for NFAs (an NFA with $F'$ instead of $F$ accepts a DIFFERENT language because of nondeterminism). So convert NFA to DFA first if needed.
5. Option B contradicts closure. Option C is wrong (regular is a SUBSET of context-free). Option D conflates with Turing-machine settings.
_Source: Jeff Erickson, "Models of Computation", §2.9 (Closure under complement)._
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?