0

In general, I have a hard time understand the REs. I have been looking for good references but none has made them clear for me so far. If anyone knows good resources, let me know. I would really appreciate it.

I was going over a reading material on RE and there are several examples i havent been able to understand

..(0 or 0(1 or 11)0)*.. no occurrence of 111

I think for there to be a match, the input has to contain either 0 or 010 or 0110 or just none (sine * makes it optional)

The book says the following are matches 0110 101011000010000101 011000011 which i have no objection to because all of them contain at least either one of the three (0 or 010 or 0110 ).

However, the book says the following are false 1110 1110110111 0101011111000011.

The book claims that ..(0 or 0(1 or 11)0)*.. means no occurrence of 111 Can someone explain to me why that is?

stratofortress
  • 453
  • 1
  • 9
  • 21
  • The regex is saying match `0`, or match `0` followed one or two `1`s, any number of times. This means no occurrence of `111`. – Tim Biegeleisen Mar 10 '16 at 04:08
  • @TimBiegeleisen so it's either `0` or `010` or `0110` any number of times but it doesnt say anything about what happens elsewhere does it? like wouldnt it be ok to have `0110111` or `101011000011100101` – stratofortress Mar 10 '16 at 04:12
  • By far the best regular expression resource is http://regular-expressions.info – Chris Kitching Mar 10 '16 at 04:14

1 Answers1

0

The actual regular expression for matching a binary number which has no more than two 1s in direct sequence is:

^(0|(0(1|11)0))*$

This regex matches any number of zeroes (the first part) or any number of the following two cases: 010 or 0110. This means that the regex will only match a single 1 or pair 11 in the sequence.

You can explore this regex here:

Regex101

Tim Biegeleisen
  • 502,043
  • 27
  • 286
  • 360
  • @stratofortress Please mark this answer correct if it solved your problem, thanks. – Tim Biegeleisen Mar 10 '16 at 07:02
  • the way i see it, matches will consist of the following: `0` `0110` `010` Then, this tells me that you are not supposed to end or start with `1`. (and you cant have `111` either). Then how comes does the book say `101011000010000101` and `011000011` are matches – stratofortress Mar 10 '16 at 15:45
  • The reason they are matches is because `0`, `010`, or `0110` can be repeated any number of times (this is what the `*` operator means). So they are matches because they consist of fragments which we know will be OK to string together. Does this make sense? – Tim Biegeleisen Mar 10 '16 at 15:48
  • what about the two dots on either side of the parentheses? doesnt this mean you have to have two digits on either side of `0` `010` and `0110` ? So `01100011` is not a match because it needs two more digits in front ? Based on your comment, it sounds like `..` and `..` front and back play no role at all so i think im still missing something – stratofortress Mar 10 '16 at 15:51
  • Actually, you may have found a flaw in the regex, in that it excludes any string which ends in `1` (and `011` is clearly acceptable). – Tim Biegeleisen Mar 10 '16 at 15:51
  • to me `011` doesnt seem acceptable because the RE has two place holders on either side. like `_ _ (0 or 010 or 0110)* _ _` – stratofortress Mar 10 '16 at 18:34
  • The `..` you see are not placeholders I believe, but rather ellipsis which just means the expression can repeat. – Tim Biegeleisen Mar 10 '16 at 23:16