Main Decidable Problems
1. Membership problem:
•
Instance:
CFG
G
,
w
Î
S
*
;
Question:
w
Î
L
(
G
)
?
2. Emptiness problem:
•
Instance:
CFG
G
;
Question:
L
(
G
) =
Æ
?
3. Finiteness problem:
•
Instance:
CFG
G
;
Question:
Is
L
(
G
)
finite
?
25
/31