Skip to main content
2 of 3
added 284 characters in body
Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186

If you have the minimal automaton, then two words are syntactically equivalent iff from any give state they lead to the same state. Therefore the syntactic monoid is the monoid generated by the transformations of the state space given by reading a letter (where functions act on the right) and two words are syntactically equivalent if they represent the same element of this monoid of transformations. They syntactic order can be understood on these transformations the following way. The transformation $u\leq v$ if the for any state $q$ the words leading from $qu$ to a final state are a subset of the words leading from $qv$ to a final state.

Alternatively you can order the states of the minimal automaton by saying $q<q’$ if every word that can reach a final state from $q$ can reach one from $q’$. Then the order on the syntactic monoid is the pointwise ordering. That is $u\leq v$ iff for each state $q$, $qu\leq qv$.

Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186