Search code examples
regextheory

Finding a regular expression

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.

Solution

  • 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