Since the transition function in can be extended to the domain , so can the set :
The advantage of this interpreation is the following: for any input words over :
which can be easily verified:
The characteristic monoid of a semiautomaton is related to the free monoid generated by in the following manner: define a binary relation on by iff . Then is clearly an equivalence relation on . It is also a congruence relation with respect to concatenation: if , then for any over :
Putting the two together, we see that if , then . We denote the congruence class in containing the word .
Now, define a map by setting . Then is well-defined. Furthermore, under , it is easy to see that is anti-isomorphic to .
If and are isomorphic semiautomata with identical input alphabet, then .
If is a homomorphic image of , so is a homomorphic image of .
- 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
- 2 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
|Date of creation||2013-03-22 19:01:10|
|Last modified on||2013-03-22 19:01:10|
|Last modified by||CWoo (3771)|