Project ForgeTheory of Computation
Finite Automata & Regular Languages
GATE 2016
Hard
Consider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ*. II. There exists a regular language A such that for all languages B, A∩B is regular. Which one of the following is CORRECT?
- AOnly I is true
- Only II is true
- CBoth I and II are true
- DBoth I and II are false
Explanation
I is FALSE: a counterexample is an NFA with a single accepting state and NO outgoing transitions at all — its language is just {ε}, not Σ* (any string requiring a transition simply has no accepting run). II is TRUE: take A=∅ (which is regular); then A∩B=∅ for every B, and ∅ is always regular.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
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.