Dyck language

From Wikipedia, the free encyclopedia

In the theory of formal languages of computer science, mathematics, and linguistics, the Dyck language (Dyck being pronounced "deek") is the language consisting of those balanced strings of parentheses [ and ]. It is important in the parsing of expressions that must have a correctly nested sequence of parentheses, such as arithmetic or algebraic expressions. It is named after the mathematician Walther von Dyck.

[edit] Formal definition

Let Σ = { [, ] } be the alphabet consisting of the symbols [ and ] and let Σ^∗ denote its Kleene closure. For any element u ∈ Σ^∗ with length |u| we define partial functions insert : Σ^∗ × (N ∪ {0}) → Σ^∗ and delete : Σ^∗ × N → Σ^∗ by

insert(u, j) = u with "[]" inserted into the jth position

delete(u, j) = u with "[]" deleted from the jth position

with the understanding that insert(u, j) is undefined for j > |u| and delete(u, j) is undefined if j > |u| − 2. We define an equivalence relation R on Σ^∗ as follows: for elements a, b ∈ Σ^∗ we have (a, b) ∈ R if and only if there exists a finite sequence of applications of the insert and delete functions starting with a and ending with b, where the empty sequence is allowed. That the empty sequence is allowed accounts for the reflexivity of R. Symmetry follows from the observation that any finite sequence of applications of insert to a string can be undone with a finite sequence of applications of delete. Transitivity is clear from the definition.

The equivalence relation partitions the language Σ^∗ into equivalence classes. If we take ε to denote the empty string, then the language corresponding to the equivalence class Cl(ε) is called the Dyck language.

[edit] Properties

The Dyck language is closed under the operation of concatenation.
By treating Σ^∗ as an algebraic monoid under concatenation we see that the monoid structure transfers onto the quotient Σ^∗/R, resulting in the syntactic monoid of the Dyck language. The class Cl(ε) will be denoted 1.
The syntactic monoid of the Dyck language is not commutative: if u = Cl([) and v = Cl(]) then uv = Cl([]) = 1 ≠ Cl(][) = vu.
With the notation above, uv = 1 but neither u nor v are invertible in Σ^∗/R.
The syntactic monoid of the Dyck language is isomorphic to the bicyclic semigroup by virtue of the properties of Cl([) and Cl(]) described above.
The Dyck language with two distinct types of parentheses can be recognized in the complexity class TC⁰.