GATE 2017 CS (CS2) – Question 49
An ε-NFA has start q₀. Transition triples (ε,a,b) are q₀:({q₂},{q₁},{q₀}); q₁:({q₂},{q₂},{q₃}); q₂:({q₀},∅,∅); q₃:(∅,∅,{q₂}). Find the extended transition δ̂(q₂,aba).
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) {q₀,q₁,q₂}
Explanation
Start with ε-closure(q₂)={q₀,q₂}. On a, move to q₁ and close to {q₀,q₁,q₂}. On b, reach q₀,q₃, whose closure is {q₀,q₂,q₃}. On the final a, only q₀ moves, reaching q₁; its closure is {q₀,q₁,q₂}. Therefore C.