• Input: G = (N, T, P, S)
• Output: Empty(X) for every X Î N È T
• Method:
• for each a
Î T: Empty(a) := Æ
• for each A Î N:
if A ® e Î P then Empty(A) := {e}
else Empty(A) := Æ
• Apply the following rule until no Empty
set can be changed:
• if A ® X1X2… Xn Î P and Empty(Xi) = {e} for all i = 1,…, n then Empty(A) = {e}