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\) ?

  1. A.

    aaaa* (𝜆+𝑏+𝑏𝑏+𝑏𝑏𝑏)

  2. B.

    aaaaa*(𝑏+𝑏𝑏+𝑏𝑏𝑏)

  3. C.

    aaaaa *(𝜆+𝑏+𝑏𝑏+𝑏𝑏𝑏)

  4. 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.

Explore the full course: Mppsc Assistant Professor