25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Allow me to leave my usual note: when providing a context-free grammar for the language at hand, you need a correctness proof which can make the approach rather unwieldy. $\endgroup$ – Raphael Jan 17 '14 at 22:21
  • $\begingroup$ For the sake of making this a proper reference question we can throw at problem dumpers, could you add an answer about coming up with grammars and automata, maybe with an example each? Thanks! $\endgroup$ – Raphael Jan 18 '14 at 19:26
  • $\begingroup$ Until the material is moved here, note that Rick Decker and babou collected some typical context-free idioms at a duplicate question. $\endgroup$ – Raphael Nov 28 '14 at 13:54
13
$\begingroup$

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:

  1. concatenation: $S\to S_1S_2$ if you can split the language in two consecutive parts use this production

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

  3. iteration: $S\to S_1S \mid \varepsilon$

Example 1

Here an 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$

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$


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).

$\endgroup$
11
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ It is undecidable whether any given language is context-free. $\endgroup$ – reinierpost May 28 '14 at 8:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.