Question 27 states the following definition of a conservative string and asks us to show that a conservative string is equivalent to a balanced string.
A string w ∈ {0, 1}* is conservative if it satisfies both of the following conditions:
– w has an equal number of 0s and 1s, and
– no prefix of w has more 0s than 1s.
However, consider the string w = 0011. This is a balanced string since w = 0x1 where x = 0y1 where y = e. However, this string is not conservative since (a) it contains an equal number of 0s and 1s but (b) 00 is a prefix of 0011 but it has more 0s than 1s.
Suggested fix (if any):
I believe the second condition in the definition of a conservative string should be "no prefix of w has more 1s than 0s"
Please verify that the error is present in the most recent revision before reporting.
This is the version of the notes linked on the front page of Algorithms.
Chapter number or note title: Strings, Models of Computation
Page number: 16
Error description:
Question 27 states the following definition of a conservative string and asks us to show that a conservative string is equivalent to a balanced string.
A string w ∈ {0, 1}* is conservative if it satisfies both of the following conditions: – w has an equal number of 0s and 1s, and – no prefix of w has more 0s than 1s.
However, consider the string w = 0011. This is a balanced string since w = 0x1 where x = 0y1 where y = e. However, this string is not conservative since (a) it contains an equal number of 0s and 1s but (b) 00 is a prefix of 0011 but it has more 0s than 1s.
Suggested fix (if any):
I believe the second condition in the definition of a conservative string should be "no prefix of w has more 1s than 0s"