Generating a Context Free Grammar(CFG) from a Language

Question

I would really appreciate if anyone could tell me how to generate CFG from this language. I am trying to learn the procedure of generating CFGs from CFLs and I am able to solve easier problems.. but I am really stuck on this one, I just can't get it how can I generate at two different positions at the same time.

L = {0^i 1^j 0^k | i + j >= 2k }

Answer 1

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:

  1. We need to allow $i+j > 2k$.
  2. 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:

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