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.