Consider the following two statements: I. If all states of an NFA are…
2016
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 \cap B\) is regular.
Which one of the following is CORRECT?
- A.
Only I is true
- B.
Only II is true
- C.
Both I and II are true
- D.
Both I and II are false
Attempted by 139 students.
Show answer & explanation
Correct answer: B
Answer: Only II is true.
Statement I: "If all states of an NFA are accepting states then the language accepted by the NFA is Σ*."
Why this is false: Acceptance requires a path that consumes the entire input. An NFA may have no transition on some symbol, so some strings cannot be consumed and are rejected. Example: an NFA with a single state q0 that is accepting but has no transitions accepts only ε, not strings like "a"; hence the language is not Σ*.
Statement II: "There exists a regular language A such that for all languages B, A ∩ B is regular."
Why this is true: Choose any finite regular language A (for example A = {a}). For any B, A ∩ B is a subset of A and therefore finite, and every finite language is regular. Thus such an A exists.
Conclusion: The first statement is false and the second is true, so the correct choice is "Only II is true."
A video solution is available for this question — log in and enroll to watch it.