0
$\begingroup$

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

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

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

$\endgroup$

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.