Context-free Grammars and Derivations

Let’s formally define context-free grammar (CFG).

Context-free grammar

A context-free grammar is a formal grammar consisting of the following:

• A set of variables (i.e., a nonterminal alphabet), $V$, one of which is a start variable.
• An alphabet, $\Sigma$, of terminal symbols.
• A set of production rules of the form $v\rightarrow s$, where $v\in V$ and $s\in (V\cup\Sigma)^*$, a string of terminals and/or variables.

Let’s look at some illustrations of CFGs for some of the languages.

Examples of CFGs

The following CFG generates the language $\{a^nb^n\;|\;n>0\}$:

As a reminder, using the alternation symbol “$\mathbf{|}$” allows us to combine all the productions for a given variable on a single line. This grammar can also be expressed as:

The smallest string in the language is $ab$, which occurs by choosing the second rule above. To generate the language $\{a^nb^n \;|\; n\geq 0\}$, we would replace $ab$ with the empty string.

To generate the language $\{a^nb^{2n} \;|\; n\geq 0\}$, we generate two $b$’s for every $a$:

We derive the string $aabbbb$ like this:

To construct a CFG for the language $\{a^ib^j\;|\;i\neq j\}$ ...