DFA

Question

construct DFA that accepts all binary numbers are divisible by either 2 or 3

Answer 1

DFA $M_1$ that accepts binary no's divisible of $2$

DFA $M_2$ that accepts binary no's divisible of $3$

Find DFA $M$ by UNION  (using cross product) that accepts binary no's divisible by $2$ or $3$

$Q\downarrow \Sigma\rightarrow$	0	1
$\rightarrow{x_0y_0}^*$	$x_0y_0$	$x_1y_1$
$x_1y_1$	$x_0y_2$	$x_1y_0$
${x_0y_2}^*$	$x_0y_1$	$x_1y_2$
${x_1y_0}^*$	$x_0y_0$	$x_1y_1$
${x_0y_1}^*$	$x_0y_2$	$x_1y_0$
$x_1y_2$	$x_0y_1$	$x_1y_2$

States having any of $x_0$ or $y_0$ are final states ( bcoz of union)

States $x_0y_0$ and $x_1y_0$ are equivalents (clearly as in table) so one of them can be removed (minimization)

Minimized DFA M 

$Q\downarrow \Sigma\rightarrow$	0	1
$\rightarrow{x_0y_0}^*$	$x_0y_0$	$x_1y_1$
$x_1y_1$	$x_0y_2$	$x_0y_0$
${x_0y_2}^*$	$x_0y_1$	$x_1y_2$
${x_0y_1}^*$	$x_0y_2$	$x_0y_0$
$x_1y_2$	$x_0y_1$	$x_1y_2$

having $5$ states 

Comments

Thank you !

Answer 2

6 states will required .