The alphabet is {0,1}, express all finite strings containing at least three 1's and at most four 0's.
I've come up with a method that enumerate every possible number of 0's:
$$111^{+}+0111^{+}+1^{+}011^{+}+111^{+}01^{*}+00111^{+}+......$$ But for three 1's and four 0's this is far too complex.
Need some help.
Here is a solution for at least $a$ 1’s and at most $b$ 0’s: $$ \sum_{a_0+\cdots+a_b=a} 1^{a_0}1^*\prod_{i=1}^b (\epsilon+0)1^{a_i}1^*, $$ where $a_0,\ldots,a_b \geq 0$ are integers. For example, when $a=b=2$ we get $$ \begin{align*} &111^*(\epsilon+0)1^*(\epsilon+0)1^*+\\ &1^*(\epsilon+0)111^*(\epsilon+0)1^*+\\ &1^*(\epsilon+0)1^*(\epsilon+0)111^*+\\ &11^*(\epsilon+0)11^*(\epsilon+0)1^*+\\ &11^*(\epsilon+0)1^*(\epsilon+0)11^*+\\ &1^*(\epsilon+0)11^*(\epsilon+0)11^*. \end{align*} $$ With more effort, you can even create an unambiguous regular expression, that is, one which corresponds to a UFA rather than an NFA; in other words, whenever there is a sum, the corresponding languages are disjoint. As an example, here is an unambiguous regular expression corresponding to $a=b=1$: $$ 1^*+11^*01^*+011^*. $$ Compare this to the ambiguous one constructed above: $$ 11^*(\epsilon+0)1^*+1^*(\epsilon+0)11^*. $$ The words $1,101$ are both captured in both summands above, but in only a single summand in the unambiguous regular expression.
