product of automata
Products of Two Automata
Let and be two automata. We define the product of and , written , as the quituple
where is a function from to , given by
Since are non-empty, is an automaton. The automaton can be thought of as a machine that runs automata and simultaneously. A pair of symbols being fed into at start state is the same as reading at state and reading at state . The set of all possible next states for the configuration in is the same as the set of all possible combinations , where is a next state for the configuration in and is a next state for the configuration in .
If and are FSA, so is . In addition, if both and are deterministic, so is , because
and is a singleton.
As usual, can be extended to read words over , and it is easy to see that
where and are words over and respectively. A word is accepted by iff is accepted by and is accepted by .
Intersection of Two Automata
Again, we assume and are automata specified above. Now, suppose . Then can be identified as the diagonal in . We are then led to an automaton
where , and are defined previously, and is given by
Suppose in addition that is finite. From the discussion in the previous section, it is evident that the language accepted by is the same as the intersection of the language accepted by and the language accepted by :
|Title||product of automata|
|Date of creation||2013-03-22 18:03:06|
|Last modified on||2013-03-22 18:03:06|
|Last modified by||CWoo (3771)|