Algorithm: Membership
•
Input:
CFG
G
= (
N
,
T
,
P
,
S
)
in Chomsky
normal form;
w
Î
T
+
•
Output:
YES
if
w
Î
L
(
G
)
NO
if
w
Ï
L
(
G
)
•
Method I:
•
if
S
Þ
n
w
, where 1
£
n
£
2
|
w
|
–
1,
then
write (’
YES
’)
else
write (’
NO
’)
•
Method II:
•
See:
The general parsing method based on CNF
The membership problem for
CFLs
is decidable
Summary:
26
/31