Examples
- Let L be the language over A = {a,b} of words of even length. The syntactic congruence has two classes, L itself and L1, the words of odd length. The syntactic monoid is the group of order 2 on {L,L1}.
- The bicyclic monoid is the syntactic monoid of the Dyck language (the language of balanced sets of parentheses).
- The free monoid on A is the syntactic monoid of the language { wwR | w in A* }, where wR denotes the reversal of word w.
- Every finite monoid is homomorphic to the syntactic monoid of some non-trivial language, but not every finite monoid is isomorphic to a syntactic monoid.
- Every finite group is isomorphic to the syntactic monoid of some non-trivial language.
- The language over {a,b} in which the number of occurrences of a and b are congruent modulo 2n is a group language with syntactic monoid Z/2n.
- Trace monoid are examples of syntactic monoids.
- Marcel-Paul Schützenberger characterized star-free languages as those with finite aperiodic syntactic monoids.
Read more about this topic: Syntactic Monoid
Famous quotes containing the word examples:
“In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
—Michel de Montaigne (1533–1592)
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)