Automata, composition of

Operations by which more complex automata are obtained from other automata by combining the initial automata in accordance with certain rules. Composition of automata plays an important role in problems of synthesis and decomposition of automata. The most important and the most frequently used compositions of automata are the direct product, superposition and feedback.

The direct product of automata $ \mathfrak A _ {i} = ( A _ {i} , S _ {i} , B _ {i} , \phi _ {i} , \psi _ {i} ) $, $ i = 1 \dots n $, is the automaton $ \mathfrak A = (A, S, B, \phi , \psi ) $ for which

$$ S = S _ {1} \times \dots \times S _ {n} ,\ A = A _ {1} \times \dots \times A _ {n} , $$

$$ B = B _ {1} \times \dots \times B _ {n} , $$

while the functions $ \phi (s, a) $ and $ \psi (s, a) $ are defined by the relations

$$ \phi ( ( s _ {1} \dots s _ {n} ), ( a _ {1} \dots a _ {n} ) ) = $$

$$ = \ ( \phi _ {1} (s _ {1} , a _ {1} ) \dots \phi _ {n} (s _ {n} , a _ {n} )), $$

$$ \psi ( ( s _ {1} \dots s _ {n} ), ( a _ {1} \dots a _ {n} ) ) = $$

$$ = \ ( \psi _ {1} (s _ {1} , a _ {1} ) \dots \psi _ {n} (s _ {n} , a _ {n} )). $$

The superposition of automata $ \mathfrak A _ {1} = (A _ {1} , S _ {1} , B _ {1} , \phi _ {1} , \psi _ {1} ) $ and $ \mathfrak A _ {2} = (B _ {1} , S _ {2} , B _ {2} , \phi _ {2} , \psi _ {2} ) $ is the automaton $ \mathfrak B = (A _ {1} , S, B _ {2} , \phi , \psi ) $ for which $ S = S _ {2} \times S _ {1} $ and

$$ \phi ( ( s _ {2} , s _ {1} ), a ) = ( \phi _ {2} ( s _ {2} , \psi _ {1} ( s _ {1} , a ) ), \phi _ {1} ( s _ {1} , a )), $$

$$ \psi ( ( s _ {2} , s _ {1} ), a ) = \psi _ {2} ( s _ {2} , \psi _ {1} ( s _ {1} , a ) ), $$

where $ (s _ {2} , s _ {1} ) \in S $ and $ a \in A _ {1} $.

In problems of completeness and synthesis of automata the feedback operation is very important. This operation is applicable to automata with $ n $ inputs and $ m $ outputs $ \mathfrak A = (A, S, B, \phi , \psi ) $ where $ A = A _ {1} \times \dots \times A _ {n} $, $ B = B _ {1} \times \dots \times B _ {m} $,

$$ \psi ( s , ( a _ {1} \dots a _ {n} )) = $$

$$ = \ ( \psi _ {1} ( s, ( a _ {1} \dots a _ {n} ) ) \dots \psi _ {m} ( s, ( a _ {1} \dots a _ {n} ) ) ), $$

such that for certain $ i, j $ the relation $ B _ {i} = A _ {j} $ is true and the function $ \psi _ {i} $ is independent of $ a _ {j} $, i.e.

$$ \psi _ {i} = \psi _ {i} ( s, ( a _ {1} \dots a _ {j-1 } , a _ {j+1 } \dots a _ {n} ) ). $$

Under these conditions, the feedback operation on the $ i $- th output and $ j $- th input of automaton $ \mathfrak A $ yields the automaton $ \mathfrak A ^ \prime = (A ^ \prime , S, B, \phi ^ \prime , \psi ^ \prime ) $ such that $ A ^ \prime = A _ {1} \times \dots \times A _ {j-1} \times A _ {j+1} \times \dots \times A _ {n} , $

$$ \phi ^ \prime (s, (a _ {1} \dots a _ {j-1} , a _ {j+1} \dots a _ {n} )) = $$

$$ = \ \phi (s, (a _ {1} \dots a _ {j-1} , $$

$$ {}{} \psi _ {i} (a _ {1} \dots a _ {j-1} , a _ {j+1} \dots a _ {n} ), a _ {j+1} \dots a _ {n} )), $$

$$ \psi ^ \prime (s, (a _ {1} \dots a _ {j-1} , a _ {j+1} \dots a _ {n} )) = $$

$$ = \ \psi (s, ( a _ {1} \dots a _ {j-1} , $$

$$ {}{} \psi _ {i} (s, ( a _ {1} \dots a _ {j-1} , a _ {j+1} \dots a _ {n} )), a _ {j+1} \dots a _ {n} )). $$

There are also other kinds of compositions of automata, e.g. the product, direct sum, semi-direct product, etc.

References[edit]

Comments[edit]

For more information see [a1].

References[edit]