Define init(L) = {u | uv is in L for some v in {0, 1}*}. In other words,…
1996
Define init(L) = {u | uv is in L for some v in {0, 1}*}. In other words, init(L) is the set of prefixes of strings in L.
Let L = {w | w is nonempty and has an equal number of 0s and 1s}. Then init(L) is
- A.
the set of all binary strings with unequal numbers of 0s and 1s
- B.
the set of all binary strings, including the null string
- C.
the set of all binary strings with exactly one more 0 than 1, or exactly one more 1 than 0
- D.
None of the above
Attempted by 6 students.
Show answer & explanation
Correct answer: B
Take any binary string u. If u has more 0s than 1s, append enough 1s to make the counts equal. If u has more 1s than 0s, append enough 0s. If u already has equal counts, append 01 so that the resulting string is nonempty and still balanced.
Therefore every binary string u is a prefix of some nonempty string in L. The null string is also a prefix, for example of 01. Hence init(L) = {0, 1}*, the set of all binary strings including the null string.