Determine the unambigious expression which generates every string in this set.
The set of all binary strings which contains 001111 as a substring.
I am thinking that the answer should be
{0,1}$^*${001111}{0,1}$^*$
But the answer says that it should be
{0,1}$^*$\{1}$^*$({00}{0}$^*${1,11,111}∪{0}{1}{1}$^*$)$^*${0}$^*$
Which is basically to take all the strings, and remove those that do not contain 001111 as a substring. Is my answer correct also, or is the 2nd one more correct?
Sorry if this is in the wrong section, as I couldn't find the Binary strings tag
Best Answer
Your answer is not correct, for the following reason: if a binary string contains more than one copy of
001111, then it can be represented as you suggest in more than one way. (For instance, the first instance of001111could be absorbed in to the first glob and the second could be the required one; or, the first instance could be the required one, and the second absorbed in to the tail.)