Regular Expression Construction

Question

I have been studying regular expressions and have been working through a tutorial which asks me to construct the following;

a regular expression for all strings containing 101 as a sub string

a regular expression for the set of all strings without any consecutive 0’s

am I correct in thinking (0 + 01)* 1* would work for the first one or am I way off the mark? And how would I approach the second one? cheers in advance

Answer 1

No you are wrong if you use (0 + 01)* 1* .This would yield :

001 00001 000111

etc... but not 101. My advise would be to just draw the diagrams.It would definitely be useful for you to see what goes on. Btw the problems that you posted don't actually require a regex :)

Answer 2

Others have pointed out that $(0+01)^*1^*$ does not match the set of strings that contain $101$ as a substring. It fails in both directions.

• Every string that matches it and contains a $0$ must begin with a $0$, so it doesn’t match $101$.
• It does match $1$.

Note that the strings that contain the substring $101$ all have the form $x101y$, where $x$ and $y$ can be any strings of zeroes and ones, possibly empty. Such strings match the regular expression $(0+1)^*$, so you want simply $(0+1)^*101(0+1)^*$.

Getting a regular expression for the strings that do not have any consecutive zeroes is a little harder. The basic idea is simple: such strings must alternate single zeroes with blocks of one or more ones. You can get a block of one or more ones with $11^*$ (or $1^+$), if you’re using that abbreviation). Thus, $0(11^*0)^*$ matches the desired strings that start and end with $0$. The ones that start with $0$ and end with $1$ are matched by $0(11^*0)^*11^*$, and you can combine these two cases as

$$0(11^*0)^*+0(11^*0)^*11^*\equiv0(11^*0)^*(\lambda+11^*)\;.$$

(Here $\lambda$ is the symbol for the empty string; you may use $\epsilon$ for it instead.)

Can you finish it up now by accounting for the strings that begin with $1$ and do not have consecutive zeroes?