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