Define init(L) = {u | uv is in L for some v in {0, 1}*}. In other words,…

PYQ GATE 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

  1. A.

    the set of all binary strings with unequal numbers of 0s and 1s

  2. B.

    the set of all binary strings, including the null string

  3. C.

    the set of all binary strings with exactly one more 0 than 1, or exactly one more 1 than 0

  4. D.

    None of the above

Attempted by 145 students.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…