Dyck language

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, D1, use 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. Let be the alphabet consisting of the symbols [ and ]. Let denote its Kleene closure. 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: 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. In yet other contexts it may instead be helpful to define the Dyck language by splitting into equivalence classes, as follows. For any element of length , we define partial functions and by is with "" inserted into the th position is with "" deleted from the th position with the understanding that is undefined for and is undefined if . We define an equivalence relation on as follows: for elements we have if and only if there exists a sequence of zero or more applications of the and functions starting with and ending with . 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 .