# Product construction for given two finite automata

I need to construct a finite automata which accept a language $L = L_1 \cap L_2$, where $L_1$ and $L_2$ are given below.

$L_1 = \{ w \mid w$ is divisible by 2 }

$L_1 = \{ w \mid w$ is divisible by 3 }

I know how to design a finite automata for a single number but how do I combine the automatons which check divisibility by 2 and 3? I am able to combine the initial states of the two automatons by using ϵ transitions from a new state but how can I combine the final states of the two automatons? Input is in the set of decimal numbers
Σ = {0,1,2,3,4,5,6,7,8,9}

• I think you need to read the product construction. courses.engr.illinois.edu/cs373/sp2010/lectures/lect_04.pdf – user35837 Mar 10 '17 at 11:37
• Please edit your question so it makes sense without people needing to read the comments. Also, what does it mean for the input to be divisible by a number? There are multiple ways in which the input could be considered to be a number, so you need to say which one applies. – David Richerby Mar 10 '17 at 11:59
• You're aware, I hope, that this problem doesn't actually need the product construction: just check for divisibility by 6. – Rick Decker Mar 23 '17 at 14:25

Here is a product construction for finite automata. I am considering you have two finite automata $$M_1$$ and $$M_2$$.

Let $$M_1$$ = $$(Q_1,\Sigma ,\delta_1,q_{01},F_1)$$ and $$M_2$$ = $$(Q_2,\Sigma ,\delta_2,q_{02},F_2)$$ be two finite automata with the same input alphabet. Let us define $$M$$ such that

$$L(M) = L(M_1) \cap L(M_2)$$

Finite automata for $$L(M)$$ is defined as $$M$$ = $$(Q,\Sigma ,\delta,q_0,F)$$ , where $$Q$$ is a finite set of states, $$\Sigma$$ is a input alphabet, $$q_0$$ is a start state, $$\delta$$ is a transition function and $$F$$ is final state of a finite automata $$M$$.

• $$Q$$ = $$Q_1$$ X $$Q_2$$ (Cartesian product),
• $$\delta((q_1,q_2),a) = (\delta_1(q_1,a),\delta_2(q_2,a))$$,
• $$q_0 = (q_{01},q_{02})$$,
• $$(q_{1},q_{2}) \in F$$ iff $$q_1 \in F_1$$ and $$q_2 \in F_2$$.

Each state in $$Q$$ is a pair consisting of a state from $$Q_1$$ and a state from $$Q_2$$.

Reference : the Product Construction for Automata by Laura Kovács.

• can you explain it with a small example? – user7511700 Mar 10 '17 at 15:54