Dyck language
The importance of using parentheses can be illustrated by looking at the following expression:
$$((21)\cdot ((1+2))\cdot 4)\xf7((1+2)\cdot 2)$$ 
There is no ambiguity in computing the result, which is $2$. If we remove all the parentheses in the expression, we get
$$21\cdot 1+2\cdot 4\xf71+2\cdot 2$$ 
which does not make much sense, unless we know the order of arithmetic operations in advance. In addition^{}, without using parentheses, the result will differ depending on how the order of operations is assigned.
Now, if we remove all the symbols in the first expression above except the parentheses, we get
$$(()(()))(())$$ 
an expression known as a word of “wellbalanced” parentheses.
Formally, let ${\mathrm{\Sigma}}_{1}=\{(,)\}$ be an alphabet consisting of the left and right parentheses. Given word $u$ over ${\mathrm{\Sigma}}_{1}$, let ${D}_{1}(u)$ be the number of occurrences of the left parentheses in $u$ minus the number of occurrences of the right parentheses in $u$.
Definition. A word $u$ over ${\mathrm{\Sigma}}_{1}$ is said to be a word of wellbalanced parentheses, if

1.
${D}_{1}(u)=0$, and

2.
${D}_{1}(v)\ge 0$ for any prefix $v$ of $u$.
For simplicity, we also say that $u$ is a wellbalanced word over ${\mathrm{\Sigma}}_{1}$.
Given this definition, the word above is wellbalanced, but $()(()))$ and $)())(($ are not.
Definition. The set of wellbalanced words over ${\mathrm{\Sigma}}_{1}$ is called the parenthesis language or Dyck language over ${\mathrm{\Sigma}}_{1}$, and is denoted by ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\mathrm{\U0001d7cf}}$.
The $1$ in ${\mathrm{\Sigma}}_{1}$ denotes that only one type of parentheses is used in the language^{}.
By induction^{}, it is not hard to see that ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\mathrm{\U0001d7cf}}$ can be generated by the following grammar^{}:

1.
terminal set is ${\mathrm{\Sigma}}_{1}$,

2.
nonterminal set is the singleton consisting of the start symbol $\sigma $,

3.
productions are $\sigma \to \lambda $ (the empty word^{}), $\sigma \to \sigma \sigma $, and $\sigma \to (\sigma )$.
As a result, ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\mathrm{\U0001d7cf}}$ is contextfree. Furthermore, ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\mathrm{\U0001d7cf}}$ is a deterministic language, and hence unambiguous.
More generally, one can consider expressions involving more than one type of parentheses, such as [], $\{\}$, and $\u27e8\u27e9$.
Definition. Let ${\mathrm{\Sigma}}_{n}=\{{{(}_{1},)}_{1},\mathrm{\dots},{{(}_{n},)}_{n}\}$ be an alphabet consisting of $n$ types of parentheses, a left and a right one for each type. The Dyck language over ${\mathrm{\Sigma}}_{n}$, written ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$, is the language generated by the following grammar:

1.
terminal set is ${\mathrm{\Sigma}}_{n}$,

2.
nonterminal set is the singleton consisting of the start symbol $\sigma $,

3.
productions are $\sigma \to \lambda $ (the empty word), $\sigma \to \sigma \sigma $, and $\sigma \to {{(}_{i}\sigma )}_{i}$ for each $i$ in $\{1,\mathrm{\dots},n\}$.
As before, ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$ is contextfree, and deterministic in particular, and hence unambiguous.
Words in ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$ are also called wellbalanced. However, it is a little more complicated to characterize what a wellbalanced word is. The two criteria above for the case $n=1$, while necessary, are not sufficient enough to describe the “wellnestedness” of parentheses when $n>1$. For example, if $n=2$, and the parentheses considered are $\{\}$ and $[]$, then the word $[\{]\}$ satisfy both criteria above, but fail to be wellnested.
In order to fully characterize a wellbalanced word over ${\mathrm{\Sigma}}_{n}$, we first define, for each $i=1,\mathrm{\dots},n$, the function ${D}_{i}$ much the same way as ${D}_{1}$: so that ${D}_{i}(u)$ is the number of left parentheses ${(}_{i}$, minus the number of right parentheses $){}_{i}$. Call a word $u$ partially balanced if, for every $i=1,\mathrm{\dots},n$:

1.
${D}_{i}(u)=0$, and

2.
${D}_{i}(v)\ge 0$ for every prefix $v$ of $u$.
Next, write $u={u}_{1}\mathrm{\cdots}{u}_{m}$, where each ${u}_{k}$ is a symbol in ${\mathrm{\Sigma}}_{n}$. Let $u(j)$ be the prefix ${u}_{1}\mathrm{\cdots}{u}_{j}$. Given a position $j$ in $u$, if ${u}_{j}$ is a left parenthesis, say ${(}_{i}$, then there is a corresponding right parenthesis $){}_{i}$ in $u$ to the right of ${u}_{j}$, positioned at, say $k$, satisfying the equation ${D}_{i}(u(j))={D}_{i}(u(k))+1$. This is a straightforward result of the two criteria above. Let ${j}^{+}$ be the least such position such that the equation holds. Now, if ${u}_{j}$ is right parenthesis, then for some position $$, we have ${k}^{+}=j$. This means that, given any position $j$ in $u$, there is a unique pair of positions $({j}_{0},{j}_{1})$, such that

•
either $j={j}_{0}$ or $j={j}_{1}$, and

•
${j}_{0}^{+}={j}_{1}$.
Define, for each $j$, the word $u[j]$ to be the subword of $u$ with starting position ${j}_{0}$ and ending position ${j}_{1}$. Now, we are ready to state the last criterion in order that $u$ be wellbalanced:

3.
for each position $j$ in $u$, the word $u[j]$ is partially balanced.
It can be shown, the set of words satisfying all three criteria above is ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$. Furthermore, if $n=1$, the third criterion can be derived from the first two criteria.
Other than being deterministic, some basic properties of ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$:

•
${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{m}}\subseteq {\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$, for any $m\le n$.

•
${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$ is monoidal (it is a monoid): $\lambda \in {\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$, and if $u,v\in {\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$, then $uv\in {\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$.

•
More generally, ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$ is insertion closed: if $u,vw\in {\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$, then $vuw\in {\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$.

•
${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$ is also deletion closed: if ${u}_{1}v{u}_{2},v\in {\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$, then ${u}_{1}{u}_{2}\in {\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$.

•
${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$ is not prefixfree.

•
Suppose $f:{\mathrm{\Sigma}}_{n}\to {\mathrm{\Sigma}}_{m}^{*}$ is a function, such that for each $i=1,\mathrm{\dots},n$, $f$ maps ${(}_{i}$ and $){}_{i}$ to some ${u}_{i}$ and ${v}_{i}$ respectively such that ${u}_{i}{v}_{i}\in {\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{m}}$. Then the extension^{} ${f}^{*}:{\mathrm{\Sigma}}_{n}^{*}\to {\mathrm{\Sigma}}_{m}^{*}$, when restricted to ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$, is a language homomorphism^{} from ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}$ to ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{m}}$.
Remark. It can be shown that the number of words of length $2n$ in ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\mathrm{\U0001d7cf}}$ is the $n$th Catalan number^{}. For a proof of this, see this entry (http://planetmath.org/ExampleOfCatalanNumbers). The idea is to visualize a word in ${\mathrm{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\mathrm{\U0001d7cf}}$ as a path in a twodimensional lattice^{}, which can be generated as follows: given a word $u$ of length $2n$, the path $p(u)$ starts from $(0,0)$ (which corresponds to the first symbol of $u$). If point $(i,j)$ is on the path, then the next point on the path is $(i+1,k)$, where $k=j+1$ if the $i$th symbol of $u$ is $($, otherwise $k=j1$. So the increase from one point to the next is either $(1,1)$, or $(1,1)$. As a result, the path $P(u)$ has the property that it never dips below the $x$axis, and it ends at $(2n,0)$. Paths defined this way are also known as Dyck paths^{}.
References
 1 D. C. Kozen, Automata and Computability, Springer, New York (1997).
 2 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation^{} to Automata, AddisonWesley, (1969).
Title  Dyck language 
Canonical name  DyckLanguage 
Date of creation  20130322 18:55:25 
Last modified on  20130322 18:55:25 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  17 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q45 
Classification  msc 68Q42 
Synonym  wellnested 
Synonym  fully balanced 
Synonym  parenthesis language 
Related topic  DyckPaths 
Related topic  ExampleOfCatalanNumbers 
Defines  wellbalanced 