Editing Syntactic monoid

{{Short description|Smallest monoid that recognizes a formal language}}
In [[mathematics]] and [[computer science]], the '''syntactic monoid''' <math>M(L)</math> of a [[formal language]] <math>L</math> is the minimal [[monoid]] that [[recognizable set|recognizes]] the language <math>L</math>. By the [[Myhill–Nerode theorem]], the syntactic monoid is unique up to unique isomorphism.

==Syntactic quotient==
An [[Alphabet (formal languages)|'''alphabet''']] is a finite [[Set (mathematics)|set]].

The [[free monoid|'''free monoid''']] on a given alphabet is the monoid whose elements are all the [[string (computer science)|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]] <math>S</math> of a free monoid <math>M</math>, one may define sets that consist of formal left or right [[Inverse element#In a unital magma|'''inverses''' of elements]] in <math>S</math>.  These are called [[Quotient of a formal language|quotients]], and one may define right or left quotients, depending on which side one is concatenating. Thus, the '''right quotient''' of <math>S</math> by an element <math>m</math> from <math>M</math> is the set
:<math>S \ / \ m=\{u\in M \;\vert\; um\in S \}.</math>

Similarly, the '''left quotient''' is

:<math>m \setminus S=\{u\in M \;\vert\; mu\in S \}.</math>

==Syntactic equivalence==
The syntactic quotient induces an [[equivalence relation]] on <math>M</math>, called the '''syntactic relation''', or '''syntactic equivalence'''  (induced by <math>S</math>).

The '''right syntactic equivalence''' is the equivalence relation

:<math>s \sim_S t \ \Leftrightarrow\ S \,/ \,s \;=\; S \,/ \,t \ \Leftrightarrow\ (\forall x\in M\colon\ xs \in S \Leftrightarrow xt \in S)</math>.

Similarly, the '''left syntactic equivalence''' is

:<math>s \;{}_S{\sim}\; t \ \Leftrightarrow\ s \setminus S \;=\; t \setminus S \ \Leftrightarrow\ (\forall y\in M\colon\ sy \in S \Leftrightarrow ty \in S)</math>.

Observe that the ''right'' syntactic equivalence is a ''left'' [[congruence relation|congruence]] with respect to [[string concatenation]] and vice versa; i.e., <math>s \sim_S t \ \Rightarrow\ xs \sim_S xt\ </math> for all <math>x \in M</math>.

The '''syntactic congruence''' or '''[[John Myhill|Myhill]] congruence'''<ref name=Hol160>Holcombe (1982) p.160</ref> is defined as<ref name=Law210>Lawson (2004) p.210</ref>

:<math>s \equiv_S t \ \Leftrightarrow\ (\forall x, y\in M\colon\ xsy \in S \Leftrightarrow xty \in S)</math>.

The definition extends to a congruence defined by a subset <math>S</math> of a general monoid <math>M</math>.  A '''disjunctive set''' is a subset <math>S</math> such that the syntactic congruence defined by <math>S</math> is the equality relation.<ref name=Law232>Lawson (2004) p.232</ref>

Let us call <math>[s]_S</math> the equivalence class of <math>s</math> for the syntactic congruence.
The syntactic congruence is [[Quotient (universal algebra)|compatible]] with concatenation in the monoid, in that one has

:<math>[s]_S[t]_S=[st]_S</math>

for all <math>s,t\in M</math>. Thus, the syntactic quotient is a [[monoid morphism]], and induces a [[quotient monoid]]

:<math>M(S)= M \ / \ {\equiv_S}</math>.

This monoid <math>M(S)</math> is called the '''syntactic monoid''' of <math>S</math>.
It can be shown that it is the smallest [[monoid]] that [[recognizable set|recognizes]] <math>S</math>; that is, <math>M(S)</math> recognizes <math>S</math>, and for every monoid <math>N</math> recognizing <math>S</math>, <math>M(S)</math> is a quotient of a [[submonoid]] of <math>N</math>. The syntactic monoid of <math>S</math> is also the [[transition monoid]] of the [[minimal automaton]] of <math>S</math>.<ref name=Hol160/><ref name=Law210/><ref name=S55>Straubing (1994) p.55</ref>

A '''group language''' is one for which the syntactic monoid is a [[Group (mathematics)|group]].<ref name=Sak342>Sakarovitch (2009) p.342</ref>

==Examples==
* Let <math>L</math> be the language over <math>A = \{a, b\}</math> of words of even length.  The syntactic congruence has two classes, <math>L</math> itself and <math>L_1</math>, the words of odd length.  The syntactic monoid is the group of order 2 on <math>\{L, L_1\}</math>.<ref name=S54>Straubing (1994) p.54</ref>  
* For the language <math>(ab+ba)^*</math>, the minimal automaton has 4 states and the syntactic monoid has 15 elements.<ref name=Law211>Lawson (2004) pp.211-212</ref>
* The [[bicyclic monoid]] is the syntactic monoid of the [[Dyck language]] (the language of balanced sets of parentheses).
* The [[free monoid]] on <math>A</math> (where <math>\left|A\right| > 1</math>) is the syntactic monoid of the language <math>\{ww^R \mid w \in A^*\}</math>, where <math>w^R</math> is the reversal of the word <math>w</math>.  (For <math>\left|A\right| = 1</math>, one can use the language of square powers of the letter.)
* Every non-trivial finite monoid is homomorphic{{clarify|Which way does the homorphism go? Is it onto?|date=June 2016}} to the syntactic monoid of some non-trivial language,<ref name=MP48>{{cite book | last1=McNaughton | first1=Robert | last2=Papert | first2=Seymour | author2-link=Seymour Papert | others=With an appendix by William Henneman | series=Research Monograph | volume=65 | year=1971 | title=Counter-free Automata | publisher=MIT Press | isbn=0-262-13076-9 | zbl=0232.94024 | page=[https://archive.org/details/CounterFre_00_McNa/page/48 48] | url-access=registration | url=https://archive.org/details/CounterFre_00_McNa/page/48 }}</ref> but not every finite monoid is isomorphic to a syntactic monoid.<ref name=Law233>Lawson (2004) p.233</ref>
* Every [[finite group]] is isomorphic to the syntactic monoid of some regular language.<ref name=MP48/>
* The language over <math>\{a, b\}</math> in which the number of occurrences of <math>a</math> and <math>b</math> are congruent modulo <math>2^n</math> is a group language with syntactic monoid <math>\mathbb{Z} / 2^n\mathbb{Z}</math>.<ref name=Sak342/>
* [[Trace monoid]]s are examples of syntactic monoids.
* [[Marcel-Paul Schützenberger]]<ref>{{cite journal | author=Marcel-Paul Schützenberger | author-link=Marcel-Paul Schützenberger | title=On finite monoids having only trivial subgroups | journal=Information and Computation| year=1965| volume=8 | issue=2 | pages=190–194|url=http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1965-4TrivialSubgroupsIC.pdf | doi=10.1016/s0019-9958(65)90108-7| doi-access=free }}</ref> characterized [[star-free language]]s as those with finite [[Aperiodic monoid|aperiodic]] syntactic monoids.<ref name=S60>Straubing (1994) p.60</ref>

==References==
{{Reflist}}
* {{cite book | last=Anderson | first=James A. | title=Automata theory with modern applications | others=With contributions by Tom Head | location=Cambridge | publisher=[[Cambridge University Press]] | year=2006 | isbn=0-521-61324-8 | zbl=1127.68049 }}
* {{cite book | last=Holcombe | first=W.M.L. | title=Algebraic automata theory | zbl=0489.68046 | series=Cambridge Studies in Advanced Mathematics | volume=1 | publisher=[[Cambridge University Press]] | year=1982 | isbn=0-521-60492-3 }}
* {{cite book | last=Lawson | first=Mark V. | title=Finite automata | publisher=Chapman and Hall/CRC | year=2004 | isbn=1-58488-255-7 | zbl=1086.68074 }}
* {{cite book | editor1-last=Rozenberg | editor1-first=G. | editor2-last=Salomaa | editor2-first=A. | first=Jean-Éric | last=Pin |author-link = Jean-Éric Pin| url=http://www.liafa.jussieu.fr/~jep/PDF/HandBook.pdf | chapter=10. Syntactic semigroups | title=Handbook of Formal Language Theory | volume=1 | publisher=[[Springer-Verlag]] | year=1997 | pages=679–746 | zbl=0866.68057 }}
* {{cite book | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 }}
* {{cite book | last=Straubing | first=Howard | title=Finite automata, formal logic, and circuit complexity | url=https://archive.org/details/finiteautomatafo0000stra | url-access=registration | series=Progress in Theoretical Computer Science | location=Basel | publisher=Birkhäuser | year=1994 | isbn=3-7643-3719-2 | zbl=0816.68086 }}

[[Category:Formal languages]]
[[Category:Semigroup theory]]