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\}$: