Consider the following regular expressions: (a) \(r=a(b+a)^*\) (b)…
2020
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:
- A.
\(L(r) \subseteq L(s) \subseteq L(t)\) - B.
\(L(r) \supseteq L(s) \supseteq L(t)\) - C.
\(L(r) \supseteq L(t) \supseteq L(s)\) - D.
\(L(s) \supseteq L(t) \supseteq L(r)\)
Attempted by 111 students.
Show answer & explanation
Correct answer: B
Key idea: simplify the expressions and compare the languages.
r = a(b+a)*. Since (b+a)* = (a+b)*, r denotes all strings that start with 'a', i.e. L(r) = a(a+b)*.
s = a(a+b)*, which is identical to L(r). So L(s) = L(r).
t = aa* b = a a* b = { a^n b | n ≥ 1 }, i.e. one or more a's followed by a single b.
Compare the languages:
Every string in L(t) has the form a^n b with n ≥ 1, so it starts with 'a'. Therefore L(t) ⊆ L(r) (and ⊆ L(s)).
There are strings in L(r) that are not in L(t), for example the string "a" is in L(r) but not in L(t) because L(t) requires a trailing 'b'. Hence the containment is proper: L(t) ⊂ L(r).
Conclusion: L(r) = L(s) and L(t) ⊂ L(r). Therefore the correct relation is L(r) ⊇ L(s) ⊇ L(t), with equality between L(r) and L(s) and strict containment for L(t).
A video solution is available for this question — log in and enroll to watch it.