Algorithm: Finiteness
•
Input:
CFG
G
= (
N
,
T
,
P
,
S
)
;
•
Output:
YES
if
L
(
G
) is finite
NO
if
L
(
G
) is infinite
•
Method:
•
Let
k
=
2
card(
N
)
•
if
there exist
z
Î
L
(
M
),
k
£
|
z
| <
2
k
then
write
(’
NO
’)
else
write (’
YES
’)
The finiteness problem for
CFLs
is decidable
Summary:
30
/31