How to prove that a language is context-free?

Question

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?

What techniques are there to prove this? Obviously, one way is to exhibit a context-free grammar for the language. Are there any systematic techniques to find a context-free grammar for a given language?

For regular languages, there are systematic ways to derive a regular grammar / finite-state automaton: for instance, the Myhill-Nerode theorem provides one way. Is there any corresponding technique for context-free languages?

---

My motivation here is to (hopefully) build up a reference question that contains a list of techniques that are often helpful, when trying to prove that a given language is context-free. Since we have many questions here that are special cases of this, it would be nice if we could document the general approach or general techniques that one can use when facing this sort of problem.

Answer 1

A practical approach that in many examples works [but not always, I know] is trying to find the nesting structure of the strings in the language. "Nested dependencies" have to be generated at the same time in different parts of the string.

Also we have the basic toolbox, the regular operations $\cdot, \cup, {}^*$ can be used within a context-free grammar:

1. concatenation: $S\to S_1S_2$ if you can split the language in two consecutive parts use this production ($S$ is the new axiom, variables $S_1,S_2$ generate the parts)

2. union: $S\to S_1 \mid S_2$ split into disjoint parts

3. iteration: $S\to S_1S \mid \varepsilon$ (again $S$ is the new axiom, the language generated from $S_1$ is repeated)

Example 1

Unequal numbers can be handled using a simple trick, splitting in "less" and "more".

$L= \{ a^mb^n \mid m\neq n \}$

Now clearly $L= \{ a^mb^n \mid m< n \} \cup \{ a^mb^n \mid m> n \}$.

Consider first half: $L_1 = \{ a^mb^n \mid m< n \}$. If there must be more $b$'s we can generate an equal numbers of $a$'s and $b$'s on the one and and add at least one extra $b$: $L_1 = \{ a^mb^m b^i \mid m\ge 0, i>0 \} = \{ a^mb^m \mid m\ge 0 \}\cdot \{ b^i \mid i>0\}$. This we can handle with concatenation from the basic toolbox.

Now the complete language also deals with the case we have more $a$'s. This we handle by using union.

$S \to S_1 \mid S_2$ (choose which part)

$S_1 \to XB$ (extra $b$ part)

$X\to aXb\mid \varepsilon$ (equal number of $a$ and $b$)

$B \to Bb \mid b$ (one or more $b$'s)

$S_2 \to AX$ (extra $a$ part)

$A \to Aa \mid a$ (one or more $a$'s)

This construction is also used to build more complicated languages, like $\{a^ib^jc^k \mid i,j,k\ge 0 \text{ and }i≠j\text{ or }i≠k\}$ as done in detail by Rick and babou here.

Example 2

$K =\{ a^kb^lc^m \mid l=m+k\}$

A first "obvious" rewrite.

$K =\{ a^kb^{m+k}c^m \mid m,k\ge 0\} = \{ a^kb^mb^kc^m \mid m,k\ge 0\}$

In linguistice this is called "cross-serial dependency": the interleaving $k,m,k,m$ (usually) strongly indicates non-contextfreeness. Of course $m+k=k+m$ and we are saved.

$K =\{ a^kb^{k+m}c^m \mid m,k\ge 0\} = \{ a^kb^kb^mc^m \mid m,k\ge 0\}$

with productions $S\to XY$, $X\to aXb\mid \varepsilon$, $Y\to bYc\mid \varepsilon$

Similarly $K'= \{ a^kb^lc^m \mid m=k+l\} = \{ a^kb^lc^lc^k \mid k,l\ge 0\}$

with productions $S\to aSc \mid X$, $X\to bXc\mid \varepsilon$

Compare the difference in nesting of the variables involved in these languages: $k,k,m,m$ is like $(_k)_k(_m)_m$, where $k,l,l,k$ is like $(_k(_l)_l)_m$.

Example 3

Using the same technique we can solve the language of strings in $1^* 0^* 1^* 0^*$ with equal numbers of $0$ and $1$, or

$K = \{ 1^n 0^m 1^k 0^p \mid n+k=m+p \} $

See elsewhere on our cs.exchange.

Example 4

Here a more complicated example for the nesting (thank you Raphael).

$L=\{b^ka^l(bc)^ma^nb^o \mid k,l,m,n,o\in {\Bbb N},k\neq o,2l=n,m\ge 2 \}$

Replace $n$ by $2l$. We can now drop $n$ in conditions.

Replace $k \neq o$ by $k > o \text{ or } k < o$ (confused? $o$ is 'oh' not 'zero'). Apply tools for union. We work with $k > o$ here. Also $k>o$ iff $k=s+o$ and $s>0$ where $s$ is a new variable. Replace $k$ by $s+o$.

$L_1 =\{b^{s+o}a^l(bc)^ma^{2l}b^o \mid l,m,o,s\in {\Bbb N},s>0,m\ge 2 \}$

Some simple rewrites.

$L_1 =\{bb^sb^o a^l bcbc(bc)^m (aa)^{l}b^o \mid l,m,o,s\in {\Bbb N} \}$

Now we see the nesting structure, and start building a grammar.

$S_1 \to TV$, $T\to bU$, $U\to bU \mid \varepsilon$ (see: concatenation and iteration here)

$V \to bVb \mid W$ (we generate $o$ $b$'s on both sides)

$W \to aWaa\mid X$

$X\to YZ$, $Y\to bcbc$, $Z\to bcZ\mid \varepsilon$

---

Final comment: these techniques help you come up with a candidate context-free grammar that will hopefully recognize your language. A correctness proof may still be needed, to ensure that the grammar really works to recognize your language (nothing more, and nothing less).

Answer 2

There is one characterisation of CFL that can be of use, the Chomsky-Schützenberger theorem.

Dyck language

Let $T$ an alphabet. We define the Dyck-language $D_T \subseteq (T \cup \hat{T})^*$ of $T$ by the context-free grammar $G = (\{S\}, T \cup \hat{T}, \delta, S)$ with $\delta$ given by

$\qquad\displaystyle S \to aS\hat{a}S \mid \varepsilon, \quad a \in T$.

Chomsky-Schützenberger theorem

$L \subseteq \Sigma^*$ is context-free if and only if there are

• an alphabet $T$,
• a regular language $R \subseteq (T \cup \hat{T})^*$ and
• homomorphism $\psi : (T \cup \hat{T}) \to \Sigma^*$

so that

$\qquad \displaystyle L = \psi(D_T \cap R)$.

Note that the homomorphism is extended to words (symbol by symbol) and then to languages (word by word).

Example

Consider $L = \{ a^n b^n c^m \mid n,m \in \mathbb{N}$. With

• $T = \{ [, \langle\}$ (and, canonically, $\hat{T} = \{ ], \rangle\}$),
• $R = \mathcal{L}([^* ]^*\langle^* \rangle^*)$ and
• $\psi(x) = \begin{cases} a, &x = [ \\ b, &x =\ ] \\ \varepsilon, &x = \langle \\ c, &x =\ \rangle \end{cases}$

the theorem implies that $L$ is context-free, in particular since

$\qquad\displaystyle D_T \cap R = \{[^n ]^n \langle^m \rangle^m \mid n,m \in \mathbb{N}\}$.

Example 2

Show that $L = \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k \neq o, 2l = n, m \geq 2 \}$ is context-free.

Here, we need one type of parentheses for $a$, one for $bc$, one for $b$, and another used to model the $b$ that cause $k \neq o$. We use

• $T = \{ [, \langle, \vdash, < \}$,
• $R = \mathcal{L}(<^+>^+\vdash^* [^* \langle\langle^+ \rangle^+\rangle ]^* \dashv^*) \cup \mathcal{L}(\vdash^* [^* \langle\langle^+ \rangle^+\rangle ]^* \dashv^*<^+>^+)$ and
• $\psi(x) = \begin{cases} b, &x \in \{\vdash, \dashv, <\} \\ a, &x = [ \\ aa, &x =\ ] \\ bc, &x = \langle \\ \varepsilon, &\text{else} \end{cases}$

and apply the theorem. In order to see that $L = \psi(D_T \cap R)$, we don't need more than the fact that matching symbols (e.g. $[$ and $]$) have to occur equally often in any $w \in D_T$. Adding this contraint to the regular expressions we defined $R$ by, we get

$\qquad \begin{align*} D_T \cap R = &\{<^p>^p \vdash^o [^l \langle^m \rangle^m ]^l \dashv^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2\} \\ &\cup\ \{\dots\} \end{align*}$

and therewith

$\qquad\begin{align*} \psi(D_T \cap R) &= \{ b^{p+o} a^l (bc)^m a^{2l} b^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2 \} \\ &\quad \cup\ \{ \dots \} \\ &= \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k > o, 2l = n, m \geq 2 \} \\&\quad \cup\ \{ \dots \} \\ &= L \;. \end{align*}$

To grammars and automata

If we want to have an automaton or grammar in the end, we have some more work ahead of us.

• Towards an automaton, construct the NPDA for $D_T$ and an NFA for $R$. The former is standard and we have algorithms for the latter, provided the language is given in a suitable representation (see also here). Intersection both is another standard construction and $\psi$ can be applied to every transition individually.

• Towards a grammar, build one for $R$ (again, should be standard), take the one for $D_T$ and intersect them. Then apply $\psi$ to the rule set (symbol for symbol).

Arguably, this is easy since algorithmic; the complexity lies in finding suitable $T$, $R$ and $\psi$. I don't know if this approach is (often) simpler than constructing PDA/grammars directly but it may allow to focus on the important features of the language at hand. Try for yourself!