Give a language $L$ over $\{0,1\}$ such that the following criteria are met:

Question

$$L=\{x\in\Sigma^{*}:\text{ both 00 and 11 are substr of x, first occurence of 00 is before first occurrence of 11}\}$$

The expression I thought of is

$R=(1+0)00(1+0)^*11(1+0)^*$

First symbol is anything, then it's followed by $00$, then any binary string, then $11$, then again any binary string.

The only problem with this regex is that it does not accept something like:

$1010|00|11$ (the $|$ is just so you can see the division better.

Also doesn't accept $0101|00|11$

So I thought of replacing $(1+0)$ with $(01+10)^*$, but then one can easily form $0110$, which is not allowed. How do I modify my regex to match this?

Answer 1

You can do $((10)^*1 + (01)^*)00(1+0)^*11(1+0)^*$. The first part should take care of any $01$ or $10$ substrings at the head.

Answer 2

This is an answer to your comment below another answer that states that you want to build a DFA : it will be easier without using regular expressions.

Indeed, $L$ can be seen as $L_1 0 L_2$ where $L_1$ is the language of strings with no $11$ that end with $0$ and $L_2$ is the language of strings that have a $11$ at some point.

The point of this decomposition is that a DFA for $L_2$ is easily found (using a regular expression or intuition); and that $L_1$ is a local language (I don't know if it's standard terminology so I'll just say what it means): it can be described by a set of starting letters (here $\{0,1\}$), authorized transitions (here $1\to 0$, $0\to 1$, $0\to 0$ are allowed, but not $1\to 1$), and a set of ending letters (here $\{0\}$).

And it's easy to build the DFA associated to a local language, so you have a DFA for $L_1$, one for $0$, and for $L_2$: all you have to do next is concatenate