Need help creating a Context-Free Grammar

Question

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\}$$

Answer 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}

Answer 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?