1
$\begingroup$

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 }

$\endgroup$
  • $\begingroup$ It might be easier to first try to come up with CFGs for simpler, related languages {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 halves 0^i1^j and 0^k. Then, for every 0 you have in the 0^k half, what would you need to balance that with in the 0^i1^j half? $\endgroup$ – roctothorpe Jan 7 '18 at 6:58
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.