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 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 described above.
- By the Chomsky–Schützenberger theorem, any context-free language is a homomorphic image of the intersection of some regular language 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 TC0.
Read more about this topic: Dyck Language
Famous quotes containing the word properties:
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)