• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Theory of Computation

Let R_1 and R_2 be regular sets defined over the alphabet Sigma. Then: A. R_1 intersection R_2 is not regular. B. R_1 union R_2 is regular. C. Sigma* - R_1 is regular. D. R_1* is not regular.

GATE 1990 · Theory of Computation · Regular Language · medium

Answer: B and C are TRUE. R_1 union R_2 is regular (option B), and Sigma* - R_1 is regular (option C).

  1. Check each option for regular language closure: A. R_1 intersection R_2 is NOT regular — FALSE. Intersection of two regular languages IS always regular (closed under intersection). B. R_1 union R_2 is regular — TRUE. Regular languages are closed under union. C. Sigma* - R_1 is regular — TRUE. Regular languages are closed under complement (swap accept/reject states in DFA). D. R_1* is NOT regular — FALSE. Kleene star of a regular language is always regular.
  2. Confirm TRUE statements: B is TRUE: If DFA M_1 accepts R_1 and DFA M_2 accepts R_2, the product construction gives a DFA for R_1 union R_2. C is TRUE: If DFA M accepts R_1, swapping accepting and non-accepting states gives a DFA for Sigma* - R_1.