Let S and T be languages over Sigma = {a, b} represented by the regular expressions (a + b*)* and (a + b)*, respectively. Which of the following is true? A. T subset S B. T = S C. S subset T D. S intersection T = phi

GATE 2000 · Theory of Computation · Regular Expression · easy

Answer: B. T = S — both (a+b*)* and (a+b)* represent Sigma*, the set of all strings over {a, b}.

1. Analyze T = (a+b)*: T = (a+b)* is the Kleene closure of the alphabet {a,b}. This is exactly Sigma* = the set of all strings over {a,b}, including the empty string.
2. Analyze S = (a+b*)*: In the expression (a+b*)*: the inner expression is (a+b*) which means 'a' or 'zero-or-more b's'. Since b* includes b^1 = b as a special case, (a+b*) generates any single character from {a,b} (among other things). The outer Kleene star (a+b*)* then generates all finite sequences of (a or b* choices). This is equivalent to all strings over {a,b} = Sigma*.
3. Compare S and T: Both S and T are equal to Sigma* — the set of all strings over {a,b}. Therefore S = T.