edited by
10,107 views
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:

  1. the set of all binary strings with unequal number of $0$’s and $1$’s

  2. the set of all binary strings including null string

  3. 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

  4. None of the above

edited by

3 Answers

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$.

edited by
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.
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.
Answer:

Related questions

23 votes
23 votes
6 answers
1
Kathleen asked Oct 9, 2014
6,204 views
If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one?$L_1.L_2$$L_1 \cap L...
17 votes
17 votes
2 answers
2
Kathleen asked Oct 9, 2014
5,541 views
Let $Q=\left( \left\{q_1,q_2 \right\}, \left\{a,b\right \}, \left\{a,b,\bot \right\}, \delta, \bot, \phi \right)$ be a pushdown automaton accepting by empty stack for the...
21 votes
21 votes
2 answers
4