M:
a
b
b
f
a
s
Question:
ab Î L(M) ?
Question:
L(M) = Æ ?
Answer: NO because s is
terminating
Answer: YES because sab |–* f, f Î F
1. qa’ ® f; q Î Q; a’ Î S: sb ® f, fa ® f
Q1 = {f} È
{s, f} = {f, s} … s is
terminating
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