Generating a context free grammar

Question

How do I generate a context free grammar for a language

$$\left\{a^ib^jc^k:i=j\text{ or }j=k,\text{ and }i,j,k\ge 0\right\}\;?$$

Thanks.

Answer 1

HINT: Write separate context-free grammars for

$$L_1=\left\{a^ib^jc^k:i=j\text{ and }i,j,k\ge 0\right\}$$

and

$$L_2=\left\{a^ib^jc^k:j=k\text{ and }i,j,k\ge 0\right\}\;,$$

making sure to use disjoint sets of non-terminal symbols. If the initial symbols of these grammars are $S_1$ and $S_2$, combine them by adding a new initial symbol $S$ and the productions $S\to S_1\mid S_2$.

Grammars for $L_1$ and $L_2$ are pretty straightforward, if you’ve seen a grammar for $$\{a^nb^n:n\ge 0\}\;;$$ it’s a standard example, so you probably have.