Language consisting of balanced strings of brackets
In the theory of formal languages of computer science, mathematics, and linguistics, a Dyck word is a balanced string of brackets. The set of Dyck words forms a Dyck language. 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.
Formal definition.
Let formula_1 be the alphabet consisting of the symbols [ and ]. Let formula_2 denote its Kleene closure.
The Dyck language is defined as:
 formula_3
Context-free grammar.
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:
 "S" → "ε" | "[" "S" "]" "S"
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:
 "S" → ("[" "S" "]")*
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.
Alternative definition.
In yet other contexts it may instead be helpful to define the Dyck language by splitting formula_2 into equivalence classes, as follows.
For any element formula_5 of length formula_6, we define partial functions formula_7 and formula_8 by
formula_9 is formula_10 with "formula_11" inserted into the formula_12th position
formula_13 is formula_10 with "formula_11" deleted from the formula_12th position
with the understanding that formula_9 is undefined for formula_18 and formula_13 is undefined if formula_20. We define an equivalence relation formula_21 on formula_2 as follows: for elements formula_23 we have formula_24 if and only if there exists a sequence of zero or more applications of the formula_25 and formula_26 functions starting with formula_27 and ending with formula_28. That the sequence of zero operations is allowed accounts for the reflexivity of formula_21. Symmetry follows from the observation that any finite sequence of applications of formula_25 to a string can be undone with a finite sequence of applications of formula_26. Transitivity is clear from the definition.
The equivalence relation partitions the language formula_2 into equivalence classes. If we take formula_33 to denote the empty string, then the language corresponding to the equivalence class formula_34 is called the Dyck language.
Generalizations.
Typed Dyck language.
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. (The counting algorithm above does not generalise).
For example, the following is a valid sentence in Dyck-3:( [ [ ] { } ] ( ) { ( ) } ) [ ]
Finite depth.
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. The depth of a sentence is the maximal depth reached within the sentence.
For example, we can annotate the following sentence with the depth at each step:0 ( 1 [ 2 [ 3 ] 2 { 3 } 2 ] 1 ( 2 ) 1 { 2 ( 3 ) 2 } 1 ) 0 [ 1 ] 0and the entire sentence has depth 3.
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.
formula_52
Examples.
We can define an equivalence relation formula_53 on the Dyck language formula_54. For formula_55 we have formula_56 if and only if formula_57, i.e. formula_10 and formula_44 have the same length. This relation partitions the Dyck language: formula_60. We have formula_61 where formula_62. Note that formula_63 is empty for odd formula_64.
Having introduced the Dyck words of length formula_64, we can introduce a relationship on them. For every formula_66 we define a relation formula_67 on formula_63; for formula_69 we have formula_70 if and only if formula_44 can be reached from formula_10 by a series of proper swaps. A proper swap in a word formula_73 swaps an occurrence of '][' with '[]'.
For each formula_74 the relation formula_67 makes formula_63 into a partially ordered set. The relation formula_67 is reflexive because an empty sequence of proper swaps takes formula_10 to formula_10. Transitivity follows because we can extend a sequence of proper swaps that takes formula_10 to formula_44 by concatenating it with a sequence of proper swaps that takes formula_44 to formula_83 forming a sequence that takes formula_10 into formula_83. To see that formula_67 is also antisymmetric we introduce an auxiliary function formula_87 defined as a sum over all prefixes formula_44 of formula_10:
 formula_90
The following table illustrates that formula_91 is strictly monotonic with respect to proper swaps.
Hence formula_92 so formula_93 when there is a proper swap that takes formula_10 into formula_95. Now if we assume that both formula_96 and formula_97, then there are non-empty sequences of proper swaps such formula_10 is taken into formula_44 and vice versa. But then formula_100 which is nonsensical. Therefore, whenever both formula_101 and formula_102 are in formula_67, we have formula_104, hence formula_67 is antisymmetric.
The partial ordered set formula_106 is shown in the illustration accompanying the introduction if we interpret a [ as going up and ] as going down.
Notes.
 ;templatestyles src="Reflist/styles.css" / ;