Let \(\delta\) denote the transition function and \(\widehat{\delta}\) denote…
2017
Let \(\delta\) denote the transition function and \(\widehat{\delta}\) denote the extended transition function of the \(\epsilon\)-NFA whose transition table is given below:
Then \(\widehat{\delta}(q_2, aba)\) is
- A.
\(\emptyset\) - B.
\(\{q_0, q_1, q_3\}\) - C.
\(\{q_0, q_1, q_2\}\) - D.
\(\{q_0, q_2, q_3 \}\)
Attempted by 113 students.
Show answer & explanation
Correct answer: C
Key idea: compute the ε-closure of the current set, then for each input symbol apply δ and take the ε-closure of the result.
Start: ε-closure(q2) = {q0, q2} because q2 ε→ q0 and q0 ε→ q2.
After reading 'a': move on 'a' from {q0, q2} gives {q1}. ε-closure({q1}) = {q0, q1, q2} since q1 ε→ q2 and q2 ε→ q0.
After reading 'b': move on 'b' from {q0, q1, q2} gives {q0, q3}. ε-closure({q0, q3}) = {q0, q2, q3} because q0 ε→ q2 (q3 has no ε-transitions).
After reading final 'a': move on 'a' from {q0, q2, q3} gives {q1}. ε-closure({q1}) = {q0, q1, q2}.
Therefore ĥδ(q2, aba) = {q0, q1, q2}.
A video solution is available for this question — log in and enroll to watch it.