You can construct the grammar using the following nonterminals:
$S$ is the initial nonterminal. We will include a production $S \to 00S0$ to capture the inequality $i+j \geq 2k$ being satisfied just using $i$.
$T$ will similarly be a nonterminal that will include a production $T \to 11T0$ which captures the inequality $i+j \geq 2k$ being satisfied just using $j$. We also add a termination production $T \to \epsilon$.
The production $S \to T$ will allow us to mix both kinds of ways to satisfy the inequality $i+j \geq 2k$. However, there are two problems:
- We need to allow $i+j > 2k$.
- We need to allow the case $i+j = 2k$ in which $i,j$ are both odd, i.e., at some point the inequality $i+j \geq 2k$ is satisfied by increasing $k$ by 1, and compensating by increasing both $i$ and $j$ by 1.
To handle the second problem, we will add a production $S \to 01T0$.
To handle the first problem for $i$, we will add the production $T \to 1T$, and to handle it for $j$, we will add the production $S \to 0S$.
In total, we obtain the following grammar:
$$
\begin{align*}
& S \to 0S \mid 00S0 \mid 01T0 \mid T \\
& T \to 1T \mid 11T0 \mid \epsilon
\end{align*}
$$
You can prove by induction the following statements:
- $T \Rightarrow^* xTy$ iff $x = 1^j$, $y = 0^k$, and $j \geq 2k$.
- As a conclusion, $T \Rightarrow^* w$ if $w = 1^j0^k$, where $j \geq 2k$.
- $S \Rightarrow^* xSy$ iff $x = 0^i$, $y = 0^k$, and $i \geq 2k$.
- As a conclusion, $S \Rightarrow^* xTy$ if either $x = 0^i$, $y = 0^k$, and $i \geq 2k$, or $x = 0^i1$, $y = 0^k$, and $i+1 \geq 2k$.
- As a conclusion from (1), $S \Rightarrow^* w$ if $w = 0^i 1^j 0^k$, where $i+j \geq 2k$.
{0^i 1^j 0^k | i + j = k }
and{0^i 1^j 0^k | i + j = 2k }
. Instead of thinking of it as generating at two different positions, consider breaking up the string you're trying to generate into two halves0^i1^j
and0^k
. Then, for every 0 you have in the0^k
half, what would you need to balance that with in the0^i1^j
half? $\endgroup$ – roctothorpe Jan 7 '18 at 6:58