regular expression

2k Views Asked by At

I would like to write the regular expression for the set of all binary strings where there are no three consecutive 0's.

The following strings are part of the language:

a) strings of the form $1,11,111,...$

b) strings $\{ 0, 01,011,0111,...\}$

d) strings $\{00, 001,0011,00111,..\}$

So,the regular expression is: $$ (1+01+001)^*$$

Is this a correct regular expression for the given language?

2

There are 2 best solutions below

2
On

A more precise expression would be

0+00+(1+01+001)*

so you will be able to accept 0 or 00...

0
On

The correct expression would be $$ (1+01+001)^*(\epsilon+0+00)$$ so that it also accepts words ending in up to two $0$s.