M:
a
b
b
f
a
s
Question: ab Î L(M) ?
sab
Question: L(M) = Æ ?
Answer: NO because s is terminating
Answer: YES because sab |–* f, f Î F
Q0 = {f}
1. qa’ ® f; q Î Q; a’ Î S: sb ® f, fa ® f
Q1 = {f} È {s, f} = {f, s} … s is terminating
|– sb
|– f, f Î F
, ...
Decidable Problems: Example
Question: Is L(M) finite?
Answer: NO because there exist z Î L(M), k £ |z| < 2k
Î L(M) , ...
 k = card(Q) = 2
All strings z Î S*: 2 £ |z| < 4: aa, bb, ab
24/26