product of automata


One way to manufacture an automaton out of existing automata is by taking productsPlanetmathPlanetmath.

Products of Two Automata

Let A1=(S1,Σ1,δ1,I1,F1) and A2=(S2,Σ2,δ2,I2,F2) be two automata. We define the product A of A1 and A2, written A1×A2, as the quituple

(S,Σ,δ,I,F):=(S1×S2,Σ1×Σ2,δ1×δ2,I1×I2,F1×F2),

where δ is a functionMathworldPlanetmath from S×Σ to P(S1)×P(S2)P(S), given by

δ((s1,s2),(α1,α2)):=δ1(s1,α1)×δ2(s2,α2).

Since S,Σ,I,F are non-empty, A is an automaton. The automaton A can be thought of as a machine that runs automata A1 and A2 simultaneously. A pair (α1,α2) of symbols being fed into A at start state (q1,q2)I is the same as A1 reading α1 at state q1 and A2 reading α2 at state q2. The set of all possible next states for the configurationMathworldPlanetmath ((s1,s2),(α1,α2)) in A is the same as the set of all possible combinationsMathworldPlanetmathPlanetmath (t1,t2), where t1 is a next state for the configuration (s1,α1) in A1 and t2 is a next state for the configuration (s2,α2) in A2.

If A1 and A2 are FSA, so is A. In addition, if both A1 and A2 are deterministicMathworldPlanetmath, so is A, because

δ((s1,s2),(α1,α2))=(δ1(s1,α1),δ2(s2,α2)),

and I is a singleton.

As usual, δ can be extended to read words over Σ, and it is easy to see that

δ((s1,s2),(a1,a2))=δ1(s1,a1)×δ2(s2,a2),

where a1 and a2 are words over Σ1 and Σ2 respectively. A word (a1,a2) is accepted by A iff a1 is accepted by A1 and a2 is accepted by A2.

Intersection of Two Automata

Again, we assume A1 and A2 are automata specified above. Now, suppose Σ1=Σ2=Δ. Then Δ can be identified as the diagonal in Σ=Σ1×Σ2=Δ2. We are then led to an automaton

A1A2:=(S,Δ,δ,I,F),

where S,I, and F are defined previously, and δ is given by

δ((s1,s2),α)=δ1(s1,α)×δ2(s2,α).

Suppose in addition that Δ is finite. From the discussion in the previous section, it is evident that the languagePlanetmathPlanetmath accepted by A1A2 is the same as the intersectionDlmfMathworldPlanetmath of the language accepted by A1 and the language accepted by A2:

L(A1A2)=L(A1)L(A2).
Title product of automata
Canonical name ProductOfAutomata
Date of creation 2013-03-22 18:03:06
Last modified on 2013-03-22 18:03:06
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 12
Author CWoo (3771)
Entry type Definition
Classification msc 03D05
Classification msc 68Q45