• 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}
Algorithm: Empty(X)
17/57