Let \(𝐿_1\) and \(𝐿_2\) be languages over \(Σ=\{𝑎,𝑏\}\) represented by the…
2020
Let \(𝐿_1\) and \(𝐿_2\) be languages over \(Σ=\{𝑎,𝑏\}\) represented by the regular expressions \((𝑎^∗+𝑏)^∗\) and \((𝑎+𝑏)^∗\) respectively.
Which of the following is true with respect to the two languages?
- A.
\(L_1 \subset L_2\) - B.
\(L_2 \subset L_1\) - C.
\(L_1 = L_2\) - D.
\(L_1 \cap L_2 = \phi\)
Attempted by 117 students.
Show answer & explanation
Correct answer: C
Answer: L1 = L2 (the two languages are equal).
Show every string in (a+b)* is in (a* + b)*: Take any string over {a,b} and split it into maximal blocks of consecutive a's and single b's. Each maximal a-block belongs to a*, and each single b is b, so the whole string is a concatenation of pieces from (a* + b). Hence it lies in (a* + b)*. Example: "abaab" can be split as "a", "b", "aa", "b".
Show every string in (a* + b)* is in (a+b)*: Each piece of (a* + b) is either a string of a's (which is in (a+b)*) or the single symbol b (also in (a+b)*). Since (a+b)* is closed under concatenation, any concatenation of such pieces belongs to (a+b)*. Therefore (a* + b)* ⊆ (a+b)*.
Combining both inclusions gives (a* + b)* = (a+b)*, so L1 = L2.
A video solution is available for this question — log in and enroll to watch it.