615 views

1 Answer

3 votes
3 votes
I believe, qi = qj is the correct answer. Here is the proof idea: Since w is non empty, assume w = ax, where 'a' is the first letter of string w and x is the remaining part(x can or cannot be empty). Clearly state q0 and qf will wind up in same state after reading first symbol of string w, since delta(q0, a) = delta(qf, a). Let us suppose that delta(q0, a) = delta(qf, a) = P. Then for both q0 and qf after scanning the first symbol 'a' they will reach state P and after reaching P, delta_hat(P, x) will be common to both of them. Hence delta_hat(q0, w) = delta_hat(qf, w).

No related questions found