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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Arka Pal Oct 9 '18 at 10:08
  • $\begingroup$ 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? $\endgroup$ – Nyte_Sorrow Oct 9 '18 at 12:37
  • $\begingroup$ 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. $\endgroup$ – orlp Oct 9 '18 at 16:15
  • $\begingroup$ It's not clear to me that your "..." even describes a finite object, and all regular expressions are finite strings. $\endgroup$ – David Richerby Oct 9 '18 at 19:16

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.