1

I'm trying to generate a CFG for the following $L$, but I'm stuck on how to do this.

$$L = \{0^i1^j2^k\mid i<j+k\}$$

Brian M. Scott
  • 616,228
Jose
  • 253

2 Answers2

2

HINT: Try using productions

$$A\to A2\mid 0A2\mid 0B2$$

and

$$B\to B1\mid \ldots\;,$$

where I’ve left some alternatives (and some other productions) for you to figure out.

Added: The CFG with productions $S\to S1$, $A\to 0S1$, and $S\to 1$ generates the language $\{0^j1^k:j<k\}$; do you see why?

Brian M. Scott
  • 616,228
  • Well, I know that some of the strings that can be created from this language include 12, 011, 00222, and 0001122. – Jose Aug 17 '13 at 01:15
  • @Jose: Let’s start with something similar but a little easier. Can you design a CFG that generates the language ${0^j1^k:j<k}$? – Brian M. Scott Aug 17 '13 at 02:24
  • I'm not sure about when we use $j$ and $k$, but if we do $0^n1^n$, then we can make a production $A -> 0A1$. – Jose Aug 17 '13 at 03:04
  • @Jose: You can use the same basic idea, but you also have to allow the non-terminal symbol to add a $1$ on the right without adding a $0$ on the left, and you have to make sure that at least one extra $1$ is generated at some point. I’ve added to my answer a CFG that does this; see if you can use the ideas embodied in it together with the original hint to come up with something. – Brian M. Scott Aug 17 '13 at 03:10
1

Since I don't know anything about context-free grammars, I'll feel free to give what might be a full solution to half the problem, or might be completely wrong. Remember that last bit: might very well be completely wrong. The good news is that I would venture to guess that even if it's wrong, it's probably not completely wrong.

Elements of $L$ look like this: $$0^{p+q}1^j2^k=0^p(0^q1^j)2^k,$$ where either:

  1. $p<k$ and $q \le j$, or

  2. $p \le k$ and $q < j$.

Option 1: \begin{array}{cl} A \to A2 \mid B2 \mid 2& \text{We can have as many $2$s at the end as we like, but at least one.}\\ B \to 0B2 \mid C \mid 02& \text{We can add $0$s to the left as we add $2$s to the right.} \\ C \to 1 \mid 01 \mid 0C1 \mid C1 &\text{We can add as many $1$s as we like, and as many zeros as $1$s.} \end{array}

dfeuer
  • 9,069