Dyck language

Example

Let $\Sigma = \set{(, )}$. The Dyck language $D_1 \subseteq \Sigma^*$ is the set of balanced strings of brackets. In such a string $w$, every prefix has at least as many $($ as $)$. The string $w$ itself has as many $($ as $)$. Its elements are the Dyck words, for example $\varepsilon$, $(\,)$, $(\,)(\,)$ and $((\,))$. More generally, $D_n$ is the language of balanced strings over $n$ kinds of bracket pairs. In $D_n$, each closing bracket must match the kind of the last unmatched opening bracket.

$D_1$ is a context-free language: it is generated by the context-free grammar with rules $S \to SS$, $S \to (S)$ and $S \to \varepsilon$. To check this, note that each rule keeps the strings balanced. Conversely, a nonempty balanced string either splits into two shorter nonempty balanced strings or has the form $(u)$ with $u$ balanced.

$D_1$ is not a regular language. Let $p$ be the pumping length of the pumping lemma for regular languages. The word $(^p\,)^p$ can only be pumped inside its first block, which unbalances it.