Let \(r=a(a+b)^*, \: s=aa^*b\) and \(t=a^*b\) be three regular expressions.…
2018
Let \(r=a(a+b)^*, \: s=aa^*b\) and \(t=a^*b\) be three regular expressions.
Consider the following :
(i) \(L(s) \subseteq L(r )\text{ and } L(s) \subseteq L(t)\)
(ii) \(L(r ) \subseteq L(s) \text{ and } L(s) \subseteq L(t)\)
Choose the correct answer from the code given below :
- A.
Only (i) is correct
- B.
Only (ii) is correct
- C.
Both (i) and (ii) are correct
- D.
Neither (i) nor (ii) is correct
Attempted by 92 students.
Show answer & explanation
Correct answer: A
Answer: Only the first statement is correct.
r = a(a+b)* — all strings over {a,b} that start with 'a' (including the string "a").
s = a a* b — strings of the form a^n b with n ≥ 1 (examples: "ab", "aab").
t = a* b — strings of the form a^n b with n ≥ 0 (examples: "b", "ab").
Show L(s) ⊆ L(r): every string in L(s) begins with an 'a', so it satisfies the pattern for L(r).
Show L(s) ⊆ L(t): every string in L(s) has the form a^n b (n ≥ 1), which is a special case of a* b, so it lies in L(t).
Show L(r) ⊄ L(s): counterexample "a" belongs to L(r) but not to L(s) (it does not end with 'b'), so L(r) is not contained in L(s).
Therefore only the first statement (L(s) ⊆ L(r) and L(s) ⊆ L(t)) is correct.
A video solution is available for this question — log in and enroll to watch it.