GATE 1996
December 6, 2023Theory-of-Computation
December 6, 2023Theory-of-Computation
| Question 33 |
Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is
| the set of all binary strings with unequal number of 0’s and 1’s | |
| the set of all binary strings including the null string | |
| the set of all binary strings with exactly one more 0’s than the number of 1’s or one more 1 than the number of 0’s | |
| None of the above |
Question 33 Explanation:
(B) is the answer. Because for any binary string of 0’s and 1’s we can append another string to make it contain equal no. of 0’s and 1’s, i.e., any string over {0,1} is a prefix of a string in L.
Correct Answer: B
Question 33 Explanation:
(B) is the answer. Because for any binary string of 0’s and 1’s we can append another string to make it contain equal no. of 0’s and 1’s, i.e., any string over {0,1} is a prefix of a string in L.