Consider the language \(L=\left\{a^{n} b^{m}: n \geq 4, m \leq 3\right\}\)…
2022
Consider the language \(L=\left\{a^{n} b^{m}: n \geq 4, m \leq 3\right\}\)
Which of the following regular expression represents language \(L\) ?
- A.
aaaa* (𝜆+𝑏+𝑏𝑏+𝑏𝑏𝑏)
- B.
aaaaa*(𝑏+𝑏𝑏+𝑏𝑏𝑏)
- C.
aaaaa *(𝜆+𝑏+𝑏𝑏+𝑏𝑏𝑏)
- D.
aaaa* (𝑏+𝑏𝑏+𝑏𝑏𝑏)
Attempted by 152 students.
Show answer & explanation
Correct answer: C
Final regular expression: a^4 a* (λ + b + bb + bbb)
Ensure at least four a's: write a^4 then allow extra a's with a* to get a^4 a*.
Allow 0 to 3 b's: use (λ + b + bb + bbb), which explicitly includes the empty string and 1–3 b's.
Combine both parts to get the language { a^n b^m : n ≥ 4, m ≤ 3 }: a^4 a* (λ + b + bb + bbb).
Equivalent compact forms: a^4 a* b^{0,3} or a^{4,} b^{0,3} (meaning at least four a's, followed by 0 to 3 b's).
Examples accepted by this expression: aaaa, aaaaa, aaaa b, aaaaa bbb.
Examples rejected: aaa (too few a's), aaaa bbbb (too many b's).
A video solution is available for this question — log in and enroll to watch it.