TITLE: Need help creating a Context-Free Grammar
QUESTION [1 upvotes]: 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\}$$

REPLY [1 votes]: 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:

$p<k$ and $q \le j$, or
$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}
{"set_name": "stack_exchange", "score": 1, "question_id": 469367}