Crafting a Context Free Grammar

Question

I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem earlier where I was to construct a CFG of $a^ib^jc^k$ with $i \ne j$ OR $j \ne k$. Obviously I separated the problem into two parts, $i$ not being $j$ and the other part being $j$ not being $k$. Taking the left part into account I wrote out the following:

$$\begin{align*} S &\to aSbTc \mid aS \mid bT \\ T &\to bTc \mid bc \\ D &\to cD \end{align*}$$ Am I correct in this for $i$ not being $j$ or is there something in my head thats wrong in thinking through this?

Answer 1

The rules like "onions" with various layers that you describe in your question can be thought of as a build order for how you will construct a string -- eg. "first I will build this part of the string, and then I will build this other part" or "I need to build these two parts at the same time in order to ensure that they are synchronized".

A good general strategy for constructing a context free grammar is to determine this build order and then have a production rule that represents each stage and/or each possibility of your build order.

You should be able to point to each nonterminal and explain the "meaning" or type of string that nonterminal is trying to construct.

For the example of $a^ib^jc^k$ with $i \ne j$, one possible build order could be:

1. Produce $a$'s and $b$'s in equal number (this is like $a^ib^j$ where $i = j$. Try writing a grammar for this first.)

2. At some point, the number of $a$'s and $b$'s have to diverge, so pick either $a$ or $b$ and produce an unbounded number of that character (this is like $a^ib^j$ where $i \ne j$. Try taking the grammar you have from 1) and adding production rules to be able to do this.)

3. Now just produce an unbounded number of $c$'s at the end. (this is the desired $a^ib^jc^k$ with $i \ne j$.)

---

A good question to ask yourself:

Why do we have to have more than one production rule to construct $a^ib^j$ where $i \ne j$? If I want the number of $a$'s and $b$'s to be equal, it makes sense that I'd have to build them at the same time, but if I want $i \ne j$, why can't I just do something like:

$S \rightarrow aS\ |\ Sb\ |\ \varepsilon$

which says "produce some number of $a$'s and then produce some number of $b$'s"?