The regular expression for the complement of the language \(L=\{a^nb^m \mid n…

Given L = { a^n b^m | n ≥ 4, m ≤ 3 } over the alphabet {a,b}.

Key idea:

• A string fails to be in L if it has fewer than four leading a's (i.e., it is of the form a^n b^m with n = 0,1,2,3).

• A string fails to be in L if it is of the form a^n b^m with m ≥ 4 (i.e., at least four b's after all a's).

• A string fails to be in L if it is not of the form a* b* — equivalently, it contains a b before an a (i.e., the substring "ba").

Construct the complement as the union of these three disjoint conditions.

Corresponding regular expressions for each case:

• Fewer than four initial a's: (λ + a + aa + aaa) b*

• At least four b's (after all a's): a* b^4 b*

• Contains a b before an a: (a+b)* b a (a+b)*

Final regular expression: ( (λ + a + aa + aaa) b* ) + ( a* b^4 b* ) + (a+b)* b a (a+b)*

Explanation: Every string not in L belongs to exactly one of these three types: it has fewer than four leading a's, it has at least four b's while being of form a* b*, or it contains the substring 'ba' (so is not of form a* b*). The union of these three regexes therefore describes the complement of L.