Skip to content

Dyck language

Properties

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

  • By treating $ \Sigma ^{} $ as an algebraic monoid under concatenation we see that the monoid structure transfers onto the quotient $ \Sigma ^{}/R $, resulting in the syntactic monoid of the Dyck language. The class $ \operatorname {Cl} (\epsilon ) $ will be denoted $ 1 $.

  • The syntactic monoid of the Dyck language is not commutative: if $ u=\operatorname {Cl} ([) $ and $ v=\operatorname {Cl} (]) $ then $ uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu $.

  • With the notation above, $ uv=1 $ but neither $ u $ nor $ v $ are invertible in $ \Sigma ^{*}/R $.

  • The syntactic monoid of the Dyck language is isomorphic to the bicyclic semigroup by virtue of the properties of $ \operatorname {Cl} ([) $ and $ \operatorname {Cl} (]) $ 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.

NOTE: 提过Dyck language，引入hierarchy。

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

  • The number of distinct Dyck words with exactly n pairs of parentheses is the n-th Catalan number.