RE: (0* + (10)*)*

The string "1" is not in the language.

Since the only '1' in the RE is grouped with the 0 in parentheses, there's no way to create a string that has a 1 but does not have a 0. (So, we can't have strings like 11, 111, 1111,...)

The string "01" is also not in the language.

Any 1 in a legal string must be followed by a 0, due to the grouping (10)

The string "10" is in the language.

We can choose 0* or (10)* from inside the parentheses. By choosing 10, we can create this string.

The string "00000000" is in the language.

Since we have the option of 0*, we can create strings of any length that have all zeros.

 

The string "00100100100" is also in the language.

To generate this string, we repeatedly choose 0* of (10)*. First, we need 2 zeros, then add a 10, then another 0, then a 10, then another 0...

The string "011011011011" is not in the language.

Again, because of the way the (10) is grouped, there's no way to generate a string that has a 1 not followed by a 0.

So, what is the description of the language?

The language includes the null string, and strings which both end in zero & have no consecutive 1's.

Another question: can you draw the FSA that corresponds to this language? answer