Reputation: 1732

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.

Upvotes: 6

Answers (6)

Sachin

Reputation: 1

It is wrong try 00110011 it must not be Satisfied But here it is satisfying Take firstly the pair 00 then take 110 Then take 011 So in whole it would be 00110011 that it is satisfying so it is wrong

Upvotes: -1

Savannah Madison

Reputation: 667

My answer would be : (1 + 01) 00 (1 + 10)**

Explanation:

The consecutive zeros shouldn't be preceded or followed by another zero. Hence 00 should be preceded by a 1 which can be either a 1 or 01. It can be followed by a 1 or 10.

Upvotes: 0

josepainumkal

Reputation: 1733

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

Upvotes: 3

Gumbo

Reputation: 655489

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

Upvotes: 8