Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Syntactic monoid
Summary
In mathematics and computer science, the syntactic monoid of a formal language is the smallest monoid that recognizes the language .
The free monoid on a given set is the monoid whose elements are all the strings of zero or more elements from that set, with string concatenation as the monoid operation and the empty string as the identity element. Given a subset of a free monoid , one may define sets that consist of formal left or right inverses of elements in . These are called quotients, and one may define right or left quotients, depending on which side one is concatenating. Thus, the right quotient of by an element from is the set
Similarly, the left quotient is
The syntactic quotient induces an equivalence relation on , called the syntactic relation, or syntactic equivalence (induced by ).
The right syntactic equivalence is the equivalence relation
Similarly, the left syntactic equivalence is
Observe that the right syntactic equivalence is a left congruence with respect to string concatenation and vice versa; i.e., for all .
The syntactic congruence or Myhill congruence is defined as
The definition extends to a congruence defined by a subset of a general monoid . A disjunctive set is a subset such that the syntactic congruence defined by is the equality relation.
Let us call the equivalence class of for the syntactic congruence.
The syntactic congruence is compatible with concatenation in the monoid, in that one has
for all . Thus, the syntactic quotient is a monoid morphism, and induces a quotient monoid
This monoid is called the syntactic monoid of .
It can be shown that it is the smallest monoid that recognizes ; that is, recognizes , and for every monoid recognizing , is a quotient of a submonoid of . The syntactic monoid of is also the transition monoid of the minimal automaton of .
A group language is one for which the syntactic monoid is a group.
The Myhill–Nerode theorem states: a language is regular if and only if the family of quotients is finite, or equivalently, the left syntactic equivalence has finite index (meaning it partitions into finitely many equivalence classes).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.