More examples

Some of the languages which we have shown not to be regular are actually context-free.

The language $\{ 0^n1^n \mid n\in\mathbb{N}\}$ is given by the following grammar

$$G=(\{S\},\{0,1\},S,\{S \to \epsilon \mid \textrm{0}S\textrm{1}\})$$

Also the language of palindromes

$$\{ ww^R \mid w\in\{\textrm{a},\textrm{b}\}^*\}$$

turns out to be context-free;

$$G=(\{S\},\{\textrm{a},\textrm{b}\},S,\{S \to \epsilon \mid \textrm{a}S\textrm{a} \mid \textrm{b}S\textrm{b}\})$$

We also note that

Theorem 5.1   All regular languages are context-free.

We don't give a proof here - the idea is that regular expressions can be translated into (special) context-free grammars, i.e. $\textrm{a}^*\textrm{b}^*$ can be translated into

$$G = (\{A,B\},\{\textrm{a},\textrm{b}\},\{ A \to aA \mid B, B \to bB \mid \epsilon )$$

(Extensions of) context free grammars are used in computer linguistics to describe real languages. As an example consider

$$\Sigma = \{ \textrm{the}, \textrm{dog}, \textrm{cat}, \textrm{which}, \textrm{bites}, \textrm{barks}, \textrm{catches} \}$$

we use the grammar $G=(\{S,N,NP,VI,VT,VP\},\Sigma,S,P)$ where

$$S \to NP VP$$

$$N \to \textrm{cat} \mid \textrm{dog}$$

$$NP \to \textrm{the} N \mid NP \textrm{which} VP$$

$$VI \to \textrm{barks} \mid \textrm{bites}$$

$$VT \to \textrm{bites} \mid \textrm{catches}$$

$$VP \to VI \mid VT NP$$

which allows us to derive interesting sentences like

the dog which catches the cat which bites barks

An important example for context-free languages is the syntax of programming languages. We have already mentioned the syntax of JAVA which uses a formalism slightly different from the one introduced here. Another example is the toy language used in the compilers course (G52CMP), see Mini-Triangle Concrete and Abstract Syntax

However, note that not all syntactic aspects of programming languages are captured by the context free grammar, i.e. the fact that a variable has to be declared before used and the type correctness of expressions are not captured.