Dyck language
In the theory of formal languages of computer science, mathematics, and linguistics, a Dyck word is a balanced string of brackets.
The simplest, Dyck-1, uses just two matching brackets, e.g. ( and ).
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.
The Dyck language is defined as: 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.
In yet other contexts it may instead be helpful to define the Dyck language by splitting
That the sequence of zero operations is allowed accounts for the reflexivity of
Symmetry follows from the observation that any finite sequence of applications of
to a string can be undone with a finite sequence of applications of
The equivalence relation partitions the language
to denote the empty string, then the language corresponding to the equivalence class
There exist variants of the Dyck language with multiple delimiters, e.g., Dyck-2 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.
For example, the following is a valid sentence in Dyck-3:( [ [ ] { } ] ( ) { ( ) } ) [ ]A Dyck language sentence can be pictured as a descent and ascent through the levels of nested brackets.
As one reads along a Dyck sentence, each opening bracket increases the nesting depth by 1, and each closing bracket decreases by 1.
We define Dyck-(k, m) as the language with k types of brackets and maximal depth m. This has applications in the formal theory of recurrent neural networks.
This relation partitions the Dyck language:
Having introduced the Dyck words of length
by a series of proper swaps.
is reflexive because an empty sequence of proper swaps takes
Transitivity follows because we can extend a sequence of proper swaps that takes
by concatenating it with a sequence of proper swaps that takes
forming a sequence that takes
is also antisymmetric we introduce an auxiliary function
is strictly monotonic with respect to proper swaps.
when there is a proper swap that takes
, then there are non-empty sequences of proper swaps such
is shown in the illustration accompanying the introduction if we interpret a [ as going up and ] as going down.
