Regex for at least three 1's and at most four 0's

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.

• I suggest you try constructing a DFA for it and then convert it into its equivalent regex. I believe that would be easier, though an extended procedure. – Arka Pal Oct 9 '18 at 10:08
• I am taught to build regex first and convert it to NFA then DFA(which is easier than regex=>DFA). I can't image how to construct DFA and conversely get regex. Could you show me how? – Nyte_Sorrow Oct 9 '18 at 12:37
• Hint: make states which keep track of the number of 0s and 1s seen so far up to 4, connect appropriately and mark the right ones as accepted. – orlp Oct 9 '18 at 16:15
• It's not clear to me that your "..." even describes a finite object, and all regular expressions are finite strings. – David Richerby Oct 9 '18 at 19:16

1 Answer

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.