Project ForgeLet δ denote the transition function and δ̂ denote the extended transition function of the ε-NFA whose transition table is given below:
State | ε | a | b q0 | {q2} | {q1} | {q0} q1 | {q2} | {q2} | {q3} q2 | {q0} | ∅ | ∅ q3 | ∅ | ∅ | {q2}
(q0 is the start state.) Then δ̂(q2, aba) is
- A∅
- B{q0, q1, q3}
- {q0, q1, q2}
- D{q0, q2, q3}
Explanation
ε-closure(q2) = {q2, q0} (q2→q0→q2 cycle). On 'a': δ(q0,a)={q1}, δ(q2,a)=∅, union={q1}; ε-closure({q1}) = {q1,q2,q0}. On 'b': δ(q0,b)={q0}, δ(q1,b)={q3}, δ(q2,b)=∅, union={q0,q3}; ε-closure = {q0,q2,q3}. On final 'a': δ(q0,a)={q1}, δ(q2,a)=∅, δ(q3,a)=∅, union={q1}; ε-closure({q1}) = {q0,q1,q2}. So δ̂(q2,aba) = {q0,q1,q2}.
Source: GATE CS 2017 (Session 2) (2017)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.