1

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?

  • 1
    No, it doesn't match 010, which has at least two 0s and at most two 1s. – parsiad Nov 22 '21 at 05:29
  • $010$ is the same as $100$. –  Nov 22 '21 at 05:31
  • That's not how regular expressions work; you're applying rules of arithmetic to your tokens to reduce them. – parsiad Nov 22 '21 at 05:32
  • I thought I can swap position like: $(0)^2(1)^2$ is the same as $0011,0101,1100,0110, \text{etc}$, or it only accepts the strings that start with $0$ ? –  Nov 22 '21 at 05:35
  • The regular expression 0011 only accepts the string 0011. – parsiad Nov 22 '21 at 05:37
  • Hi, a similar question was asked before. See https://math.stackexchange.com/questions/747525/fsm-to-be-regular-with-atleast-two-0s-and-at-most-two-1s – phdstudent Nov 22 '21 at 05:40
  • I thought it would be possible to swap their positions, as long as there are $2$ 0s and $2$ 1s, but it turns out that their positions cannot be swapped –  Nov 22 '21 at 05:41
  • @Elif, I don't know what FSM means. –  Nov 22 '21 at 05:42
  • 1
    Finite state machine – parsiad Nov 22 '21 at 05:43
  • The string 010 is different from the string 001, because in general a "word" in a language is an ordered sequence of symbols – Rob Nov 22 '21 at 06:36

1 Answers1

2

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.

Rob
  • 6,727
  • I don't know regular expression can include $\varepsilon$, but the DFA doesn't have $\varepsilon$. –  Nov 22 '21 at 06:55
  • @hello Does that matter, if the goal is to find a regular expression for the language? – Rob Nov 22 '21 at 07:04
  • I think $0(0+\varepsilon)^(1+\varepsilon)0(0+\varepsilon)^(1+\varepsilon)(0+\varepsilon)^*$ is enough to cover all your possible strings. –  Nov 22 '21 at 07:53
  • 1
    @hello That expression doesn't match the string 0011; you have implicitly assumed that there is always a 0 between the two 1 symbols, which is not a stipulation of the language – Rob Nov 22 '21 at 08:48