Give a regex that matches this specific language:

Question

$$L=\{a : \text{both 101 and 010 are substrings of a}\}$$

Let alphabet $\Sigma=\{0,1\}$

The regex I thought of was the following.

$$R=(0+1)^*(101(0+1)^*010(0+1)^* + 010(0+1)^*101(0+1)^*)$$

The $(0+1)^*$ at the very left says that the language can start with any number of $0's/1's$.

$101(0+1)^*010(0+1)^*$ says the following:

We start with the string $101$, followed by any number of $0's/1's$, followed by the string $010$, followed by any number of $0's/1's$.

$ 010(0+1)^*101(0+1)^*$ says the following:

We start with the string $010$, followed by any number of $0's/1's$, followed by the string $101$, followed by any number of $0's/1's$.

As there are two possible combinations, we $or$ with a $+$. Is this good? Can I make my regex shorter?

Answer 1

You are missing two strings $0101$ and $1010$ which can be added explicitly to the regex. You can also somewhat simplify the regex by concatenating the common expression $(0+1)^*$ so it would be

$$R=(0+1)^*(101(0+1)^*010+ 010(0+1)^*101+0101+1010) (0+1)^*$$