GATE CS 2000 Q1.4 — Regular Expressions and Finite Automata

To determine the relationship between the languages $S$ and $T$, let us analyze the strings generated by their respective regular expressions over the alphabet $\Sigma = \{a, b\}$.

1. Language $T = (a+b)^*$:

   This is the standard regular expression representing the set of all possible strings over $\{a, b\}$, including the empty string $\epsilon$. Thus, $T = \Sigma^*$.

2. Language $S = (a+b^*)^*$ :

   Let us check if we can generate the basic symbols $a$ and $b$ from the inner expression $(a+b^*)$:

   • By choosing the first term, we can generate $a$.
   • By choosing the second term $b^*$ and selecting the exponent $1$, we can generate $b$.

   Since the inner expression $(a+b^*)$ can generate both $a$ and $b$, its Kleene closure $(a+b^*)^*$ can generate any sequence of $a$'s and $b$'s. Therefore, $S$ also represents the set of all possible strings over $\{a, b\}$, i.e., $S = \Sigma^*$.

Since both languages generate the set of all strings over $\{a, b\}$:

Hence, the correct option is C.