1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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 of 001111 could 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.)

$\endgroup$
  • $\begingroup$ Ah that's what I forgot. I forgot that this needs to be an unambiguous expression. I get it now :) Now I just need to know how to formulate this decomposition. Thanks! $\endgroup$ – nonion Jul 2 '13 at 18:41
  • $\begingroup$ Why would the expression $\{0.999\cdots,1\} = \{1\}$ be wrong? I guess what I mean is that the same thing can have two or more different representations. What is wrong with that? $\endgroup$ – Lord Soth Jul 2 '13 at 18:51
  • $\begingroup$ @LordSoth Unless I completely miss my guess, he's essentially been asked to come up with a way of counting binary strings of this type. As such, each such string needs a unique representation. $\endgroup$ – Nick Peterson Jul 2 '13 at 18:54
  • $\begingroup$ @LordSoth (I base this assumption on the generating-function tag, on the use of the term 'unambiguous', and on his seeming agreement with my answer. But I could be wrong!) $\endgroup$ – Nick Peterson Jul 2 '13 at 18:55
  • $\begingroup$ @nrpeterson OK, thank you, I was just wondering if there is an important convention that I was not aware regarding these binary strings. I shall perhaps check it out later. $\endgroup$ – Lord Soth Jul 2 '13 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.