Consider the non-deterministic finite automaton (NFA) shown in the figure.…
2005
Consider the non-deterministic finite automaton (NFA) shown in the figure.
State X is the starting state of the automaton. Let the language accepted by the NFA with Y as the only accepting state be L1. Similarly, let the language accepted by the NFA with Z as the only accepting state be L2. Which of the following statements about L1 and L2 is TRUE?
- A.
L1 = L2
- B.
L1 ⊂ L2
- C.
L2 ⊂ L1
- D.
None of the above
Attempted by 113 students.
Show answer & explanation
Correct answer: A
Answer: L1 = L2.
Reason: Show that for every input string w, the set of states reachable from the start contains Y exactly when it contains Z. We prove this by induction on the length of the input.
Key observation: the transition function (restricted to relevant transitions) is
From X: on 0 → {Y, Z}; on 1 → {X}.
From Y: on 0 → {Y, Z}; on 1 → ∅.
From Z: on 0 → {X}; on 1 → {Y, Z}.
Base case: for the empty string ε the set reachable from the start is {X}, so neither Y nor Z is reachable; the property holds.
Inductive step: assume after reading some prefix u the reachable set R(u) satisfies (Y ∈ R(u)) ⇔ (Z ∈ R(u)). Consider reading one more symbol a (either 0 or 1). The new reachable set is R(ua) = ⋃_{s∈R(u)} δ(s,a).
If a = 0: any contribution to Y comes from either X or Y (both of which also contribute Z on 0), while Z can contribute X on 0 but that does not produce Y. Thus Y ∈ R(ua) iff Z ∈ R(ua).
If a = 1: only Z contributes Y (and Z contributes both Y and Z on 1); X contributes X on 1 and Y contributes nothing on 1. Hence Y ∈ R(ua) iff Z ∈ R(ua).
Therefore by induction the invariant holds for all input strings: after reading any string w from the start, Y is reachable iff Z is reachable. Since acceptance with Y as the only accepting state means Y is reachable, and acceptance with Z as the only accepting state means Z is reachable, the two languages are identical. Hence L1 = L2.
A video solution is available for this question — log in and enroll to watch it.