I am trying to figure out the CFG of a given language.
For $a^ib^jc^k :j = i + k$
I found a solution something like below.
$$\begin{align}
S_0 &\to aS_1bS_2
\mid S_1bS_2c
\mid\epsilon \\
S_1 &\to aS_1b
\mid\epsilon\\
S_2 &\to bS_2c \mid \epsilon \\
\end{align}
$$
But when the condition is $j \le i + k$ I cannot figure out how should I modify my CFG.
Best Answer
Here's a slightly simplified grammar for the equality condition:
$$\begin{align} S&\to S_1 S_2\\ S_1&\to a S_1 b \mid \epsilon\\ S_2&\to b S_2 c \mid \epsilon \end{align} $$
In effect, this ensures that an $b$ is added whenever either an $a$ or a $c$ is added. For the condition $\le$ instead of $=$, we instead add at most one $b$ instead of exactly one time:
$$\begin{align} S&\to S_1 S_2\\ S_1&\to a S_1 b \mid a S_1\mid\epsilon\\ S_2&\to b S_2 c \mid S_2 c\mid\epsilon \end{align} $$
Similarly, for the $\ge$ condition, we want to make sure that at least one $b$ is added: $$\begin{align} S&\to S_1 S_2\\ S_1&\to a S_1 b \mid S_1 b\mid\epsilon\\ S_2&\to b S_2 c \mid b S_2\mid\epsilon \end{align} $$
These patterns are quite useful if you're playing the "write me a CFG game". More importantly, they might provide some insight into how pushdown automata work (and why they're called pushdown automata), and even into how to think recursively.