2
Consider the following regular expressions:
(a) $r=a(b+a)^*$
(b) $s=a(a+b)^+$
(c) $t=aa^*b$
Choose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above:
Solution
For $r=a(b+a)^*$:
This represents all strings over $\{a,b\}$ that start with $a$.
So,
$L(r)=\{a,aa,ab,aaa,aab,aba,\ldots\}$
For $s=a(a+b)^+$:
Here, after first $a$, at least one more symbol from $\{a,b\}$ must be present.
So, $s$ represents all strings over $\{a,b\}$ that start with $a$ and have length at least $2$.
Therefore,
$L(s)\subseteq L(r)$
For $t=aa^*b$:
This represents strings of the form:
$ab,aab,aaab,aaaab,\ldots$
So, every string of $L(t)$ starts with $a$ and has length at least $2$.
Therefore,
$L(t)\subseteq L(s)$
Hence,
$L(r)\supseteq L(s)\supseteq L(t)$