GATE CS 2016 Set 2 Q42 — Regular Expressions and Finite Automata

Let us analyze both statements individually:

Statement I: False

In a Deterministic Finite Automata (DFA) where all states are accepting, the language accepted is indeed $\Sigma^*$ (since a DFA must have a transition defined for every alphabet symbol from every state). However, this does not hold for a Non-deterministic Finite Automata (NFA).

An NFA can have missing transitions. If a string leads to a state with no defined transition for the next symbol, the NFA gets "stuck" and rejects the string, even if all its states are accepting.

Counterexample:

• Let $\Sigma = \{a\}$.
• Consider an NFA with a single state $q_0$ which is both the start state and an accepting state, with no transitions defined.
• The language accepted by this NFA is $L = \{\epsilon\}$, which is not equal to $\Sigma^* = \{a\}^*$.

Statement II: True

We need to find at least one regular language $A$ such that for any language $B$ (regular or non-regular), the intersection $A \cap B$ is guaranteed to be regular.

• Let $A = \emptyset$ (the empty language, which is regular).
• For any language $B$, we have: $$A \cap B = \emptyset \cap B = \emptyset$$
• Since $\emptyset$ is a regular language, the intersection is always regular.

Note: More generally, any finite language $A$ also satisfies this condition because the intersection of any language with a finite language is always finite, and all finite languages are regular.

Conclusion

Only Statement II is true. Therefore, the correct option is B.