In the theory of formal languages of computer science, mathematics, and linguistics, a **Dyck word** is a balanced string of square brackets [ and ]. The set of Dyck words forms the **Dyck language**.

Dyck words and language are named after the mathematician Walther von Dyck. They have applications in the parsing of expressions that must have a correctly nested sequence of brackets, such as arithmetic or algebraic expressions.

# Formal definition

It may be helpful to define the Dyck language via a context-free grammar in some situations.
The Dyck language is generated by the context-free grammar with a single non-terminal *S*, and the production:

That is, *S* is either the empty string (*ε*) or is "[", an element of the Dyck language, the matching "]", and an element of the Dyck language.

An alternative context-free grammar for the Dyck language is given by the production:

That is, S* is zero or more occurrences of the combination of "[", an element of the Dyck language, and a matching "]", where multiple elements of the Dyck language on the right side of the production are free to differ from each other.*

# Properties

- The Dyck language is closed under the operation of concatenation.
- By treating as an algebraic monoid under concatenation we see that the monoid structure transfers onto the quotient , resulting in the
**syntactic monoid of the Dyck language**. The class will be denoted . - The syntactic monoid of the Dyck language is not commutative: if and then .
- With the notation above, but neither nor are invertible in .
- The syntactic monoid of the Dyck language is isomorphic to the bicyclic semigroup by virtue of the properties of and described above.
- By the Chomsky–Schützenberger representation theorem, any context-free language is a homomorphic image of the intersection of some regular language with a Dyck language on one or more kinds of bracket pairs.
^{[1]} - The Dyck language with two distinct types of brackets can be recognized in the complexity class .
^{[2]} - The number of distinct Dyck words with exactly
*n*pairs of parentheses is the*n*-th Catalan number.

# Examples

# Generalizations

There exist variants of the Dyck language with multiple delimiters, e.g., on the alphabet "(", ")", "[", and "]". The words of such a language are the ones which are well-parenthesized for all delimiters, i.e., one can read the word from left to right, push every opening delimiter on the stack, and whenever we reach a closing delimiter then we must be able to pop the matching opening delimiter from the top of the stack.

# See also