Dyck language

From HandWiki
Short description: 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, D1, 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 [math]\displaystyle{ \Sigma = \{ [, ] \} }[/math] be the alphabet consisting of the symbols [ and ]. Let [math]\displaystyle{ \Sigma^{*} }[/math] denote its Kleene closure. The Dyck language is defined as:

[math]\displaystyle{ \{ u \in \Sigma^* \vert \text{ all prefixes of } u \text{ contain no more ]'s than ['s} \text{ and the number of ['s in } u \text{ equals the number of ]'s}\}. }[/math]

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 [math]\displaystyle{ \Sigma^{*} }[/math] into equivalence classes, as follows. For any element [math]\displaystyle{ u \in \Sigma^{*} }[/math] of length [math]\displaystyle{ | u | }[/math], we define partial functions [math]\displaystyle{ \operatorname{insert} : \Sigma^{*} \times \mathbb{N} \rightarrow \Sigma^{*} }[/math] and [math]\displaystyle{ \operatorname{delete} : \Sigma^{*} \times \mathbb{N} \rightarrow \Sigma^{*} }[/math] by

[math]\displaystyle{ \operatorname{insert}(u, j) }[/math] is [math]\displaystyle{ u }[/math] with "[math]\displaystyle{ [] }[/math]" inserted into the [math]\displaystyle{ j }[/math]th position
[math]\displaystyle{ \operatorname{delete}(u, j) }[/math] is [math]\displaystyle{ u }[/math] with "[math]\displaystyle{ [] }[/math]" deleted from the [math]\displaystyle{ j }[/math]th position

with the understanding that [math]\displaystyle{ \operatorname{insert}(u, j) }[/math] is undefined for [math]\displaystyle{ j \gt |u| }[/math] and [math]\displaystyle{ \operatorname{delete}(u, j) }[/math] is undefined if [math]\displaystyle{ j \gt |u| - 2 }[/math]. We define an equivalence relation [math]\displaystyle{ R }[/math] on [math]\displaystyle{ \Sigma^{*} }[/math] as follows: for elements [math]\displaystyle{ a, b \in \Sigma^{*} }[/math] we have [math]\displaystyle{ (a, b) \in R }[/math] if and only if there exists a sequence of zero or more applications of the [math]\displaystyle{ \operatorname{insert} }[/math] and [math]\displaystyle{ \operatorname{delete} }[/math] functions starting with [math]\displaystyle{ a }[/math] and ending with [math]\displaystyle{ b }[/math]. That the sequence of zero operations is allowed accounts for the reflexivity of [math]\displaystyle{ R }[/math]. Symmetry follows from the observation that any finite sequence of applications of [math]\displaystyle{ \operatorname{insert} }[/math] to a string can be undone with a finite sequence of applications of [math]\displaystyle{ \operatorname{delete} }[/math]. Transitivity is clear from the definition.

The equivalence relation partitions the language [math]\displaystyle{ \Sigma^{*} }[/math] into equivalence classes. If we take [math]\displaystyle{ \epsilon }[/math] to denote the empty string, then the language corresponding to the equivalence class [math]\displaystyle{ \operatorname{Cl}(\epsilon) }[/math] is called the Dyck language.

Properties

  • The Dyck language is closed under the operation of concatenation.
  • By treating [math]\displaystyle{ \Sigma^{*} }[/math] as an algebraic monoid under concatenation we see that the monoid structure transfers onto the quotient [math]\displaystyle{ \Sigma^{*} / R }[/math], resulting in the syntactic monoid of the Dyck language. The class [math]\displaystyle{ \operatorname{Cl}(\epsilon) }[/math] will be denoted [math]\displaystyle{ 1 }[/math].
  • The syntactic monoid of the Dyck language is not commutative: if [math]\displaystyle{ u = \operatorname{Cl}([) }[/math] and [math]\displaystyle{ v = \operatorname{Cl}(]) }[/math] then [math]\displaystyle{ uv = \operatorname{Cl}([]) = 1 \ne \operatorname{Cl}(][) = vu }[/math].
  • With the notation above, [math]\displaystyle{ uv = 1 }[/math] but neither [math]\displaystyle{ u }[/math] nor [math]\displaystyle{ v }[/math] are invertible in [math]\displaystyle{ \Sigma^{*} / R }[/math].
  • The syntactic monoid of the Dyck language is isomorphic to the bicyclic semigroup by virtue of the properties of [math]\displaystyle{ \operatorname{Cl}([) }[/math] and [math]\displaystyle{ \operatorname{Cl}(]) }[/math] 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 [math]\displaystyle{ TC^{0} }[/math].[2]
  • The number of distinct Dyck words with exactly n pairs of parentheses and k innermost pairs (viz. the substring [math]\displaystyle{ [\ ] }[/math]) is the Narayana number [math]\displaystyle{ \operatorname{N}(n, k) }[/math].
  • The number of distinct Dyck words with exactly n pairs of parentheses is the n-th Catalan number [math]\displaystyle{ C_n }[/math]. Notice that the Dyck language of words with n parentheses pairs is equal to the union, over all possible k, of the Dyck languages of words of n parentheses pairs with k innermost pairs, as defined in the previous point. Since k can range from 0 to n, we obtain the following equality, which indeed holds:
[math]\displaystyle{ C_n = \sum_{k=1}^n \operatorname{N}(n, k) }[/math]

Examples

Lattice of the 14 Dyck words of length 8 - [ and ] interpreted as up and down

We can define an equivalence relation [math]\displaystyle{ L }[/math] on the Dyck language [math]\displaystyle{ \mathcal{D} }[/math]. For [math]\displaystyle{ u,v\in\mathcal{D} }[/math] we have [math]\displaystyle{ (u,v)\in L }[/math] if and only if [math]\displaystyle{ |u| = |v| }[/math], i.e. [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] have the same length. This relation partitions the Dyck language: [math]\displaystyle{ \mathcal{D} / L = \{\mathcal{D}_0,\mathcal{D}_1,\ldots\} }[/math]. We have [math]\displaystyle{ \mathcal{D} = \mathcal{D}_{0} \cup \mathcal{D}_{2} \cup \mathcal{D}_{4} \cup \ldots = \bigcup_{n=0}^{\infty} \mathcal{D}_{n} }[/math] where [math]\displaystyle{ \mathcal{D}_{n} = \{ u\in\mathcal{D} \mid |u| = n\} }[/math]. Note that [math]\displaystyle{ \mathcal{D}_{n} }[/math] is empty for odd [math]\displaystyle{ n }[/math].

Having introduced the Dyck words of length [math]\displaystyle{ n }[/math], we can introduce a relationship on them. For every [math]\displaystyle{ n \in \mathbb{N} }[/math] we define a relation [math]\displaystyle{ S_{n} }[/math] on [math]\displaystyle{ \mathcal{D}_{n} }[/math]; for [math]\displaystyle{ u,v\in\mathcal{D}_{n} }[/math] we have [math]\displaystyle{ (u,v)\in S_{n} }[/math] if and only if [math]\displaystyle{ v }[/math] can be reached from [math]\displaystyle{ u }[/math] by a series of proper swaps. A proper swap in a word [math]\displaystyle{ u\in\mathcal{D}_{n} }[/math] swaps an occurrence of '][' with '[]'. For each [math]\displaystyle{ n\in\mathbb{N} }[/math] the relation [math]\displaystyle{ S_{n} }[/math] makes [math]\displaystyle{ \mathcal{D}_{n} }[/math] into a partially ordered set. The relation [math]\displaystyle{ S_{n} }[/math] is reflexive because an empty sequence of proper swaps takes [math]\displaystyle{ u }[/math] to [math]\displaystyle{ u }[/math]. Transitivity follows because we can extend a sequence of proper swaps that takes [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math] by concatenating it with a sequence of proper swaps that takes [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] forming a sequence that takes [math]\displaystyle{ u }[/math] into [math]\displaystyle{ w }[/math]. To see that [math]\displaystyle{ S_{n} }[/math] is also antisymmetric we introduce an auxiliary function [math]\displaystyle{ \sigma_{n}:\mathcal{D}_{n}\rightarrow\mathbb{N} }[/math] defined as a sum over all prefixes [math]\displaystyle{ v }[/math] of [math]\displaystyle{ u }[/math]:

[math]\displaystyle{ \sigma_n(u) = \sum_{vw=u} \Big( (\text{count of ['s in } v) - (\text{count of ]'s in } v) \Big) }[/math]

The following table illustrates that [math]\displaystyle{ \sigma_{n} }[/math] is strictly monotonic with respect to proper swaps.

Strict monotonicity of [math]\displaystyle{ \sigma_{n} }[/math]
partial sums of [math]\displaystyle{ \sigma_{n}(u) }[/math] [math]\displaystyle{ P }[/math] [math]\displaystyle{ P-1 }[/math] [math]\displaystyle{ P }[/math] [math]\displaystyle{ Q }[/math]
[math]\displaystyle{ u }[/math] [math]\displaystyle{ \ldots }[/math] ] [ [math]\displaystyle{ \ldots }[/math]
[math]\displaystyle{ u' }[/math] [math]\displaystyle{ \ldots }[/math] [ ] [math]\displaystyle{ \ldots }[/math]
partial sums of [math]\displaystyle{ \sigma_{n}(u') }[/math] [math]\displaystyle{ P }[/math] [math]\displaystyle{ P+1 }[/math] [math]\displaystyle{ P }[/math] [math]\displaystyle{ Q }[/math]
Difference of partial sums 0 2 0 0

Hence [math]\displaystyle{ \sigma_{n}(u') - \sigma_{n}(u) = 2 \gt 0 }[/math] so [math]\displaystyle{ \sigma_{n}(u) \lt \sigma_{n}(u') }[/math] when there is a proper swap that takes [math]\displaystyle{ u }[/math] into [math]\displaystyle{ u' }[/math]. Now if we assume that both [math]\displaystyle{ (u,v), (v,u)\in S_{n} }[/math] and [math]\displaystyle{ u\ne v }[/math], then there are non-empty sequences of proper swaps such [math]\displaystyle{ u }[/math] is taken into [math]\displaystyle{ v }[/math] and vice versa. But then [math]\displaystyle{ \sigma_{n}(u) \lt \sigma_{n}(v) \lt \sigma_{n}(u) }[/math] which is nonsensical. Therefore, whenever both [math]\displaystyle{ (u,v) }[/math] and [math]\displaystyle{ (v,u) }[/math] are in [math]\displaystyle{ S_{n} }[/math], we have [math]\displaystyle{ u = v }[/math], hence [math]\displaystyle{ S_{n} }[/math] is antisymmetric.

The partial ordered set [math]\displaystyle{ D_{8} }[/math] is shown in the illustration accompanying the introduction if we interpret a [ as going up and ] as going down.

Generalizations

There exist variants of the Dyck language with multiple delimiters, e.g., D2 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).

See also

Notes

  1. ↑ Kambites, Communications in Algebra Volume 37 Issue 1 (2009) 193-208
  2. ↑ Barrington and Corbett, Information Processing Letters 32 (1989) 251-256

References



Retrieved from "https://handwiki.org/wiki/index.php?title=Dyck_language&oldid=3381144"