Skip to main content
2 of 2
Fully Math Jaxed
Daniele Tampieri
  • 6.4k
  • 7
  • 30
  • 45

Understanding Syntactic Congruence & Order

Reading through Jean-Eric Pin's "Mathematical Foundations of Automata Theory". Love this book. However, I am confused by the following section, and am hoping for some clarity and more examples if possible. I need this for my research.

Syntactic order definition

I am not sure exactly how it is used to create the syntactic order in the following example:

Example

Putting the above example into this automaton:

  • $Q = \{1,2,3\}$
  • $I = \{1\}$
  • $F = \{3\}$
  • $A = \{a,b\}$
  • $E = \{(1,a,2),(2,a,2),(2,b,3),(3,b,3),(3,a,2)\}$

For the above statements $u \le v $ and $s, t \in A*$, $$ sut \in L \implies svt \in L $$ Would this look like the following from the example above?

$(1,a,2) \implies (1,aa,2)$

Does this define the relations from the example above? That is, are the relations from the example above (i.e. '$aa = a$', etc.) syntactic congruence?

And, how are they used to define the syntactic order?