Question 52

Analyze Statement I: 'If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma^*$.'
Unlike a standard DFA which must have a transition defined for every input symbol from every state, an NFA transition function maps to subsets of states: $\delta(q, a) \subseteq Q$. If an NFA state has no transition on a symbol $a$, any string reading $a$ from that state crashes and is rejected.
For example, consider an NFA with alphabet $\Sigma = \{a, b\}$ having a single state $q_0$ (which is an accepting start state) with a transition $\delta(q_0, a) = \{q_0\}$ and no transition on $b$. The language accepted by this NFA is $a^*$, which is strictly a subset of $\Sigma^*$. Thus, Statement I is FALSE.

Analyze Statement II: 'There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular.'
Consider the empty language $A = \emptyset$. The empty language is regular because it is recognized by a finite automaton with no accept states. For any language $B$ over the same alphabet (whether regular, context-free, recursive, or undecidable):

Since $\emptyset$ is regular, $A \cap B$ is always regular for every language $B$. Thus, such a regular language $A$ exists. Statement II is TRUE.

Therefore, only Statement II is true.