Context-free language

Question

Given $L= \lbrace w \in \lbrace 0, 1 \rbrace^* \ : \ |w|_0 \leq |w|_1 \leq 2 |w|_0 \rbrace$, where $|w_0|$ is number of zeros in $w$.

Is $L$ context-free?

Answer 1

Another context-free grammar $G=(V=\{ S \}, \Sigma=\{0,1\}, R, S)$ to try: \begin{align} S \to & S10 \mid S01 \mid 10S \mid 1S0 \mid 0S1 \mid 10S \, \mid \\ & S110 \mid 1S10 \mid 11S0 \mid 110S \, \mid \\ & S101 \mid 1S01 \mid 10S1 \mid 101S \, \mid \\ & S011 \mid 0S11 \mid 01S1 \mid 011S \, \mid \\ & \epsilon \end{align}

• The first line covers all possibilities to place one $0$ and one $1$ plus one growth point.

• Lines $2$ to $4$ cover all possibilities to place one $0$ and two $1$ plus one growth point.

• Line $5$ handles the stop of growth of the word.

$L(G) \subseteq L$, the tricky bit is to show $L \subseteq L(G)$.

Looking from a different angle, we can build $L$ by induction over the number of $0$ symbols. \begin{align} L_0 = & \{ \epsilon \} \\ L_{i+1} = & L_i 10 \cup L_i 01 \cup 10 L_i \cup 1L_i0 \cup 0L_i1 \cup 10L_i \, \cup \\ & L_i110 \cup 1L_i10 \cup 11L_i0 \cup 110L_i \, \cup \\ & L_i101 \cup 1L_i01 \cup 10L_i1 \cup 101L_i \, \cup \\ & L_i011 \cup 0L_i11 \cup 01L_i1 \cup 011L_i \end{align} where $u L v = \{ uwv \mid w \in L \}$. The question is, does this result in the same $L$ as $$ \DeclareMathOperator{insert}{insert} \begin{align} L_0 = & \{ \epsilon \} \\ L_{i+1} = & \insert(\insert(L_i, j, 0), k, 1) \, \cup \\ & \insert(\insert(\insert(L_i, j, 0), k, 1), l, 1) \end{align} $$ for all feasible insert positions $j,k$ or $j,k,l$.