Strings over an alphabet S

lBasis: l, the empty string, is in S*.

lInductive rule: If x ë S* and s ë S, then s x (s followed by x) is in S*.