Project ForgeSign up free
Theory of Computation
Finite Automata & Regular Languages
GATE 2007
Hard

Which of the following is TRUE?

  • AEvery subset of a regular set is regular
  • Every finite subset of a non-regular set is regular
  • CThe union of two non-regular sets is not regular
  • DInfinite union of finite sets is regular

Explanation

(A) is false (a subset of a regular language, like Σ*, can be any language). (C) is false (e.g. {aⁿbⁿ} and its complement are both non-regular, but their union Σ* is regular). (D) is false (any language, including non-regular ones, can be written as an infinite union of finite sets — its individual strings). (B) is TRUE: every finite language is regular, regardless of what larger (possibly non-regular) set it's drawn from.

Source: GATE CS 2007 (2007)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free