Dyck language
Encyclopedia
In the theory of formal languages of computer science
, mathematics
, and linguistics
, the Dyck language is the language consisting of 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
.
s insert : Σ∗ × (N ∪ {0}) → Σ∗ and delete : Σ∗ × N → Σ∗ by
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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, and linguistics
Linguistics
Linguistics is the scientific study of human language. Linguistics can be broadly broken into three categories or subfields of study: language form, language meaning, and language in context....
, the Dyck language is the language consisting of balanced strings of parentheses [ and ]. It is important in the parsing
Parsing
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
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
Walther von Dyck
Walther Franz Anton von Dyck , born Dyck and later ennobled, was a German mathematician...
.
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 functionPartial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...
s 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
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
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
Reflexive relation
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...
of R. Symmetry
Symmetric relation
In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...
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
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
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.
Properties
- The Dyck language is closed under the operation of concatenationConcatenationIn computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
. - By treating Σ∗ as an algebraic monoidMonoidIn abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
under concatenation we see that the monoid structure transfers onto the quotient Σ∗/R, resulting in the syntactic monoidSyntactic monoidIn mathematics and computer science, the syntactic monoid M of a formal language L is the smallest monoid that recognizes the language L.-Syntactic quotient:...
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 semigroupBicyclic semigroupIn mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. Although it is in fact a monoid, it is usually referred to as simply a semigroup. The first published description of this object was given by Evgenii Lyapin in 1953. Alfred H...
by virtue of the properties of Cl([ ) and Cl(] ) described above. - By the Chomsky–Schützenberger theoremChomsky–Schützenberger theoremIn formal language theory, the Chomsky–Schützenberger theorem is a statement about the number of words of a given length generated by an unambiguous context-free grammar. The theorem provides an unexpected link between the theory of formal languages and abstract algebra...
, any context-free languageContext-free languageIn formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
is a homomorphic image of the intersection of some regular languageRegular languageIn theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
with a homomorphic preimage of the Dyck language on two parentheses. - The Dyck language with two distinct types of parentheses can be recognized in the complexity class TC0TC0TC0 is a complexity class used in circuit complexity. It is the first class in the hierarchy of TC classes.TC0 contains all languages which are decided by Boolean circuits with constant depth and polynomial size, containing only unbounded-fanin AND gates, OR gates, and majority gates...
.