# I need to present a regular expression for the following languages:

1. L2 = E{0,1)

All the words in L2 with equal number of 0's and 1's and every prex of w has at most two more of either 0's or 1's.

2. All words that does not contain “bbb” as substring.

i think this is :( e + b + bb)(a + ab + abb)*

-
I'm not sure if you're a native speaker. Hoewever, could you please correct your spelling? Especially the description of 1. is quite unclear to me. –  tohecz Nov 27 '12 at 14:46

## migrated from math.stackexchange.comNov 27 '12 at 21:59

This question came from our site for people studying math at any level and professionals in related fields.

Your point 2, is obviously correct.

As for the point 1, we construct the automaton: let's remember how much more 0's we've read than 1's. Then we have transitions:

S0  by 0 to S1
S0  by 1 to S-1
S1  by 0 to S2
S1  by 1 to S0
S-1 by 0 to S0
S-1 by 1 to S-2
S2  by 1 to S1
S-2 by 0 to S-1


S0 is initial, only S0 is final. This way we are sure, that in whatever state we are, the number of $0$'s and $1$'s that were read so far differs by at most $2$ and in the final state the number are the same.

Then the language is $$\Bigl(0(01)^*1+1(10)^*0\Bigr)^*$$

The large parenthesis corresponds to all paths from S0 to S0, and we can repeat it as many times as needed.

-
I hope I understood the question correctly. –  tohecz Nov 27 '12 at 14:59
Nice answer. +1 –  Rick Decker Nov 27 '12 at 21:06