Dyck Language - Properties

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)