Reputation: 294

Regular expressions: contains at least two 0s but not consecutive 0s

Is the solution of this exercise the below regular expression? I found it in the internet but I don't believe that this is correct.

(1*011*(0+011*))*

According to the theory of Chapter 1 in the book "The handbook of computational linguistics and natural language processing", how could I solve this exercise?

I would like a regular expression that will satisfy the below regular language

    L = {010,0101,0110,0101010,01011110,.....}

Upvotes: 0

Answers (8)

kishore A

Reputation: 11

(1+01)* 0 (1+) 0 (1+10)*

This solves the problem

Upvotes: 1

ORISI GAYATRI

Reputation: 1

Given language contains at least two zeroes but not consecutive zeroes.

The strings accepted by this language are L= {010,0101,0110,0101010,01011110,.....}

The matching regular expression is:

1*01*(10+101*)^+

Here + represents at least a one time occurrence.

DFA for the above language is shown in this link:

DFA IMAGE

Upvotes: 0

Marwa

Reputation: 1

1*01(1|01)*01*

I think this would work perfectly

Upvotes: 0

Nidhi Donuru

Reputation: 1

If it's atleast 2 0s, then there's also a possibility of 1 being at the start So wouldn't that be 1* 0 1* 0 (1+01)* But if it's acc to the language given (the 2 0s at the beginning and end), 0 (1+01)* 0

Upvotes: 0

Luis Colorado

Reputation: 12668

The regexp you post is erroneous, it suffices to note that it has a 0+ subsequence, which should admit a sequence of one or more 0s. It can be corrected with this solution:

1*011*0(10?)*

or with + operator

1*01+0(10?)*

An explanation of it should be: First skip al the ones that start your expression with the 1* subpattern, so you get to the first 0, then skip at least one 1, and all the 1s following it (with subpattern 1+) up to the second 0, so we have just matched the minimum length string that matches you regular language. Once here, all the rest is optional, we need to repeat any number of times the pattern 1 with an optional trailing 0 (as in 10?), or there should be two consecutive 0s. You can check it in this demo, that contains all the possible strings from 1 to 8 characters, and the matching or not of them.