# Give a regex that matches this specific language:

$$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?

• You're forgetting that the two substrings can overlap, so you need to generate, say, 11101000 too. – Henning Makholm Jul 16 '17 at 21:18
• @HenningMakholm how can I add that in? That seems tough to incorporate – K Split X Jul 16 '17 at 21:46

## 1 Answer

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)^*$$