Just like groups and rings, a semiautomaton can be viewed as an algebraic structure. As such, one may define algebraic constructs such as subalgebras and homomorphisms. In this entry, we will briefly discuss the former.
A semiautomaton is said to be a subsemiautomaton of a semiautomaton if
The last inclusion means the following: for all . We write when is a subsemiautomaton of .
A subsemiautomaton of is said to be proper if , and is written .
Examples. Let be a semiautomaton.
can be represented by its state diagram, which is just a directed graph. Any strongly connected component of the state diagram represents a subsemiautomaton of , characterized as a semiautomaton such that any state in can be reached from any other state in . In other words, for any , there is a word over such that either , where is the restriction of to . A semiautomaton whose state diagram is strongly connected is said to be strongly connected.
Suppose is strongly connected. Then has no proper subsemiautomaton whose input alphabet is equal to the input alphabet of . In other words, if , then . However, proper subsemiautomata of exist if we take for any proper subset of , provided that . In this case, is just the restriction of to the set .
Specializations to Other Machines
Note: the following notations are used: given an automaton and a state-output machine , let and be the associated semiautomaton . So and may be written and respectively.
Definition (automaton). is a subautomaton of if
Definition (state-output machine). is a submachine of if
where and are the state and input alphabets of .
- 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
|Date of creation||2013-03-22 19:01:03|
|Last modified on||2013-03-22 19:01:03|
|Last modified by||CWoo (3771)|
|Defines||strongly connected semiautomaton|