I'm trying to build a regular expression for this language:
$$L=\{w\in\{0,1\}^*: \text{at least two} \ 0's \ \text{and at most two} \ 1's\}$$
So, it's mean that this language has $|w|_0 \geq2$ and $|w|_1 \leq 2$, this is what I have come up:
$$100(0)^*+1100(0)^*+00(0)^*$$
Is this regular expression correct?
Best Answer
The language specifies each word can have at most two ones; this part is easy to specify. It is captured, for example, by the following expression.
$$(1 + \varepsilon) \cdot (1 + \varepsilon)$$
If there were no restriction on the number of allowed $0$s, you could complete the expression by inserting three $(0 + \varepsilon)^*$ terms into the above expression. However, the language also stipulates that there must be at least two zeroes. To have exactly two zeroes is also not difficult to brute-force; they could only go in 6 possible places between/around the $1$s.
$$00(1 + \varepsilon) (1 + \varepsilon) + 0(1 + \varepsilon)0 (1 + \varepsilon) + 0(1 + \varepsilon) (1 + \varepsilon)0 + \cdots + (1+\varepsilon)(1+\varepsilon)00$$
A complete description of the target language could be obtained by inserting $(0 + \varepsilon)^*$ into each possible position between symbols in each of the six terms above. The resulting expression is huge and unwieldy, but finite, proving the language is regular. It is almost certainly possible to obtain a simpler expression with a cleverer idea.