# For example lets say you were trying to (a) write a regular expression for the language A of binary strings whose length is divisible by three (b) the language B of all binary strings that do not contain two consecutive 1's. Where would I start?

For example lets say you were trying to
(a) write a regular expression for the language A of binary strings whose length is divisible by three
(b) the language B of all binary strings that do not contain two consecutive 1's.
Where would I start?
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Kitamiliseakekw
Step 1
One very straightforward approach to (a) is to begin by listing the 8 binary strings of length 3. Every string whose length is a multiple of 3 must be formed by concatenating those strings. I’ll illustrate with strings of even length: any string of even length can be segmented into two-character chunks, each of which must be 00,01,10, or 11, so the binary strings of even length are described by the regular expression $\left(00+01+10+11{\right)}^{\ast }$. (You may use some other symbol than + to indicate alternatives; common alternatives are ∣, $\vee$, and $\cup$.)
Step 2
Problem (b) is a little harder. The condition says that if a string contains a 1 at all, that 1 must either be the last symbol in the string or be followed immediately by a 0. Ignore for a moment the exceptional case of a final 1; if we just require that every 1 be followed immediately by a 0, we’re allowing precisely those strings that can be built by concatenating 0’s and 10’s, i.e., the strings described by the regular expression $\left(0+10{\right)}^{\ast }$. We’d like to have all of those strings, but also all strings that consist of one of those followed by a single 1; how can you modify or extend the regular expression to include the latter type as well as the former?