Finding a regular expression

Question

I have a simple question about finding a regular expression for a given language.

I am given the language L where:

L = {w ∈ {0, 1}* : w has exactly one pair of consecutive zeros}

My first attempt at this was to try L( (0 + 1)* 00 (0 + 1)*), but I noticed the problem with that would be with where I have (0 + 1)* because if 0 is chosen, it can be zero more more of them, thus leading to more than one pair of consecutive zeros.

I also know, that the possible cases I have are, two zeros in the front, in the middle, and at the end. I just am not quite sure how to create a regular expression for that.

Any help is much appreciated.

Answer 1

Try this:

1* (011*)* 00 (11*0)* 1*

An explanation:

• 1*: any amount of leading 1’s
• (011*)*: if there is a 0 before the 00, it must not be followed by another 0, thus only one or more 1’s are allowed; this pattern may be repeated any number of times
• 00: the two 0’s
• (11*0)*: if there is a 0 after the 00, it must not preceded by another 0, thus only one or more 1’s; this pattern may be repeated any number of times
• 1*: any amount of trailing 1’s

Answer 2

The best possible answer for this problem is (1 + 01)* 00 (1 + 10)*