Let S and T be languages over Σ = {a, b} represented by the regular…
2000
Let S and T be languages over Σ = {a, b} represented by the regular expressions (a + b*)* and (a + b)*, respectively. Which of the following is true?
- A.
S ⊂ T
- B.
T ⊂ S
- C.
S = T
- D.
S ∩ T = ∅
Attempted by 19 students.
Show answer & explanation
Correct answer: C
T = (a + b)∗ is exactly Σ∗, the set of all strings over {a, b}.
For S = (a + b∗)∗, note that b∗ can generate ε, b, bb, and so on. In particular, b∗ can generate the single symbol b. Therefore the expression inside the outer Kleene star can generate both a and b. Repeating those pieces can form any string over {a, b}, so S also equals Σ∗.
Hence S = T. Option C is correct.