-1
$\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$
  • 1
    $\begingroup$ I think you need to read the product construction. courses.engr.illinois.edu/cs373/sp2010/lectures/lect_04.pdf $\endgroup$ – aaag Mar 10 '17 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$ – David Richerby Mar 10 '17 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$ – Rick Decker Mar 23 '17 at 14:25
1
$\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 : https://www.complang.tuwien.ac.at/lkovacs/ATCSNotes/atcs_h2.pdf

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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