2. ABSTRACT AUTOMATA
Def. A Mealy type automaton is a quintuple where
: S I S
: S I S
: S x I S
: Sx IO
Def. An automaton is a subautomaton of the automaton if and only if
Def. Two automata and are isomorphic if and only if there exist three one-to-one onto mappings
Def. An automaton is a homomorphic image of the automaton if and only if there exists three onto mappings
Example of homomorphism
Def. If and
are two Mealy (Moore) automata, then the states
and are said to
be equivalent iff
for all .
NB! A1=A2 - equivalence relation on the set of states
2.5.1. Lemma: Equivalent states s1 and s2 of automata A1 and A2 go into equivalent states under each input.
2.5.2. Equivalence of automata
Def. Two automata are equivalent if s1ÎS1 has an equivalent state and each has an equivalent state .
2.5.3. Reduced automaton
Def. An automaton A is reduced if s1 equivalent to s2 implies that s1=s2.
Def. An automaton A' is said to be a realization of automaton A if there exists a subautomaton of A' which is isomorphic (homomorphic) to A.
Last update: 3 August, 2004