Writing regular expressions for these languages?

Question

The following languages over the alphabet Σ = {0, 1} are all regular:

L = { w | w is of even length and begins with 01 }

L = { w | the numbers of 1's in w is multiple of 3 }

L = { w | w does not contain the substring 10 }

I am asked to write regular expressions for these languages, but I don't know how to do so. Can anyone give me advice on how to approach these problems?

Answer 1

L = { w | w is of even length and begins with 01 }

Ans: 01((0 + 1)(0 + 1))*

Explanation: 01 itself of even length to, we can suffix any even length string consist of 0s and 1s.

L = { w | the numbers of 1's in w is multiple of 3 }

Ans: (0*10*10*10*)*

Explanation: 0 can appear any number of time anywhere in string the restriction is over 1 it should be in multiple of 3 so * over three 1.

L = { w | w does not contain the substring 10 }

Ans: 0*1*

Explanation: string can't contain 10 means only 1 is allow after any 1.

Answer 2

Here are some hints:

1. You can use the expression (0 ∪ 1) to mean "0 or 1," and (0 ∪ 1)(0 ∪ 1) to mean "any two-character string." Can you form all even-length regular expressions from the second of those expressions? Can you then see how to get from there to the language you need?

2. Any string with a number of 1s that's a multiple of three can be subdivided into a bunch of smaller strings, each of which consists of three 1s with 0's interspersed. Can you make all strings with exactly three 1's in them? From there, can you get the language you need?

3. This is actually the easiest of the bunch. Write out a few strings that don't contain 10. Notice anything? As a hint, you can do this with four characters.

Hope this helps!