M = (Q, S, R, s, F), where: Q = {s, q1, q2, f}, S = {a},
R = {sa ® q1, sb ® q2, q1a ® q2, q1b ® f}, F = {f}
Rt = {sa ® q1, sb ® q2, q1a ® q2, q1b ® f}
Nonterminating States: Example
Q0 = {f}
1) qd ® f; q Î Q; d Î S: q1b ® f
Q1 = {f} È {q1} = {f, q1}
2) qd ® f  ; q Î Q; d Î S: q1b ® f
    qd ® q1; q Î Q; d Î S: sa   ® q1 
Q2 = {f, q1} È {q1, s} = {f, q1, s}
3) qd ® f;   q Î Q; d Î S: q1b ® f
    qd ® q1; q Î Q; d Î S: sa   ® q1 
    qd ® s;   q Î Q; d Î S: none
Q3 = {f, q1, s} È {q1, s} = {f, q1, s} = Q2 = Qt
30/44