44 votes 44 votes Define a context free languages $L \in \{0, 1\}^*$, $\text{init} (L) = \{u \mid uv \in L$ for some $v$ in $\{0, 1\}^*\}$ ( in other words, $\text{init}(L)$ is the set of prefixes of $L$) Let $L = \{w \mid w \text{ is nonempty and has an equal number of $0$’s and $1$’s}\}$ Then $\text{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 null string the set of all binary strings with exactly one more $0$ than the number of $1$’s or one more $1$ than the number of $0$’s None of the above Theory of Computation gate1996 theory-of-computation context-free-language normal + – Kathleen asked Oct 9, 2014 edited Jan 29, 2018 by kenzou Kathleen 10.1k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Show 10 previous comments keshore muralidharan commented Aug 8, 2020 reply Follow Share (B) is the answer.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. 0 votes 0 votes svas7246 commented Jul 22, 2021 i edited by svas7246 Jul 22, 2021 reply Follow Share @harrypotter0 difference between Vϵ{0,1} and Vϵ{0,1}* is Vϵ{0,1} Here it indicates there should be a non-null string and Vϵ{0,1}* presence of star indicates it can even generate a null here 0 votes 0 votes varunrajarathnam commented Jul 22, 2021 reply Follow Share @keshore muralidharan when ‘w’ is already equal number of 0’s and 1’s how can you make it equal again by appending 0 or 1? 0 votes 0 votes Please log in or register to add a comment.
Best answer 50 votes 50 votes Correct Option: B Because for any binary string of $0$'s and $1$'s we can append another string to make it contain equal number of $0$'s and $1$'s. i.e., any string over $\{0,1\}$ is a prefix of a string in $L$. Example: $01111$ - is prefix of $01111000$ which is in $L$. $1111$- is prefix of $11110000$ which is in $L$. $01010$- is prefix of $010101$ which is in $L$. Arjun answered Oct 15, 2014 edited May 5, 2021 by soujanyareddy13 Arjun comment Share Follow See all 14 Comments See all 14 14 Comments reply Show 11 previous comments Ruchi Vora commented Jan 19, 2020 reply Follow Share I think because even epsilon means equal no of 1's and 0's . So prefix of epsilon is epsilon . 0 votes 0 votes yashpalsingh commented Aug 10, 2020 reply Follow Share init(L) contains epsilon because epsilon is also a prefix of strings in L. for example : prefix of 1010 -> epsilon, 1, 10, 101, 1010 . every string contains epsilon as a prefix. 3 votes 3 votes shashankrustagi commented Dec 1, 2020 reply Follow Share I am happy i also thought like that 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes every string is a prefix of itself, hence in init we have all the strings of L also so all other answers except B are ruled out. Radha mohan answered Nov 21, 2018 Radha mohan comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Prefixes means any number of leading symbols can be considered along with the string itself. Here as L belongs to {0,1}* , so epsilon should be considered too, which is only satisfied by option B. Hence, the option B is correct answer. ankit3009 answered Jan 13, 2021 ankit3009 comment Share Follow See all 0 reply Please log in or register to add a comment.