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:
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (18961966)
“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 (16701733)
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (16881744)
Related Phrases
Related Words