Algorithm: Membership Problem
•
Input:
DFA
M
= (
Q
,
S
,
R
,
s
,
F
)
;
w
Î
S
*
•
Output:
YES
if
w
Î
L
(
M
)
NO
if
w
Ï
L
(
M
)
•
Method:
•
if
sw
|
–
*
f
,
f
Î
F
then
write (’
YES
’)
else
write (’
NO
’)
The membership problem for FA
s
is decidable
Summary:
21/26