↑ arvau

Wikipedia / 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, 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

denote its Kleene closure. The Dyck language is defined as:

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 , 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.

Alternative definition

, we define partial functions by

  1. th position

  2. th position

. We define an equivalence relation if and only if. That the sequence of zero operations is allowed accounts for the reflexivity. Symmetry. Transitivity is clear from the definition.

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 (with matching delimiters colored the same):

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.

Properties

  • The Dyck language is closed under the operation of concatenation.

  • 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 syntactic monoid of the Dyck language is not commutative.

  • .

  • The syntactic monoid of the Dyck language is isomorphic to the bicyclic semigroup 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.

  • The Dyck language with two distinct types of brackets can be recognized in the complexity class TC^{0}.

  • The number of distinct Dyck words with exactly pairs of parentheses and innermost pairs (viz. the substring) is the Narayana number.

  • Dyck words are isomorphic to Dyck paths, a subset of staircase walk symbols

  • The number of distinct Dyck words with exactly pairs of parentheses is the -th Catalan number. Notice that the Dyck language of words with parentheses pairs is equal to the union, over all possible , of the Dyck languages of words of parentheses pairs with innermost pairs, as defined in the previous point. Since can range from 0 to , we obtain the following equality, which indeed holds:

Examples

.

by a series of proper swaps into a partially ordered set is reflexive. Transitivity is also antisymmetric we introduce an auxiliary function:

is strictly monotonic with respect to proper swaps. is antisymmetric.

is shown in the illustration accompanying the introduction if we interpret a [ as going up and ] as going down.

See also

Notes

References