Algorithm: Emptiness
•
Input:
CFG
G
= (
N
,
T
,
P
,
S
)
;
•
Output:
YES
if
L
(
G
)
=
Æ
NO
if
L
(
G
)
¹
Æ
•
Method:
•
if
S
is nonterminating
then
write (’
YES
’)
else
write (’
NO
’)
The emptiness problem for
CFLs
is decidable
Summary:
29
/31