2
$\begingroup$

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}

$\endgroup$
3
  • 1
    $\begingroup$ I think you need to read the product construction. courses.engr.illinois.edu/cs373/sp2010/lectures/lect_04.pdf $\endgroup$
    – user35837
    Commented Mar 10, 2017 at 11:37
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 10, 2017 at 11:59
  • $\begingroup$ You're aware, I hope, that this problem doesn't actually need the product construction: just check for divisibility by 6. $\endgroup$ Commented Mar 23, 2017 at 14:25

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ can you explain it with a small example? $\endgroup$ Commented Mar 10, 2017 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.