Algorithm: Emptiness Problem
•
Input:
FA
M
= (
Q
,
S
,
R
,
s
,
F
)
;
•
Output:
YES
if
L
(
M
)
=
Æ
NO
if
L
(
M
)
¹
Æ
•
Method:
•
if
s
is nonterminating
then
write (’
YES
’)
else
write (’
NO
’)
The emptiness problem for FA
s
is decidable
Summary:
22/26