How to construct compound Automata ? and find the no of states in minimal FA ?

Question

Construct Minimal FA that accept all binary strings ends with 01 AND length of string is EVEN .
Also find no of states in its minimal FA

Answer 1

The above problem is Intersection of Two problems 

1. All binary strings ending with 01, having regular expressoin $(0+1)^*01$, having DFA $M_1$

2. All binary strings of even length , having regular expression $((0+1)(0+1))^*$ , having DFA $M_2$

Take Intersection of $M_1$ and $M_2$, using cross product, having $x_0y_0$ as start state and $x_2y_0$ as final states( where we have both finals together)

$Q$\ $\Sigma$	$0$	$1$
$\rightarrow x_0y_0$	$x_1y_1$	$x_0y_1$
$x_1y_1$	$x_1y_0$	$x_2y_0$
$x_0y_1$	$x_1y_0$	$x_0y_0$
$x_1y_0$	$x_1y_1$	$x_2y_1$
$x_2y_0^*$	$x_1y_1$	$x_0y_1$
$x_2y_1$	$x_1y_0$	$x_0y_0$

Minimized DFA will be 

 

$Q$\ $\Sigma$	$0$	$1$
$\rightarrow x_0y_0$	$x_1y_1$	$x_0y_1$
$x_1y_1$	$x_0y_0$	$x_2y_0$
$x_0y_1$	$x_0y_0$	$x_0y_0$
$x_2y_0^*$	$x_1y_1$	$x_0y_1$

Comments

@praveen_saini Sir i got same diagram. 
[ R has to be final state . I have taken U . which needs correction . still i atached image 2  . if drawn properly will get same as ur answer  ]

It is very time consuming . any alternative approach ?

image1

image 2

---

you can design it directly 

by taking transition from start to final with 01 , q0 x 0 -> q1, q1 x 1 -> q2 

now for dfa find the transitions for remaining symbols such that we reach final with given conditions,

such as q2 x 0 -> q1 , such that length remains even and we ends with 11.

finally we have answer try to analyse it , it will help , but need very good practice. 

---

@Praveen Sir

Any shortcut to reach to final table i.e. minimized table from the original table after taking the cross product .

---

do we have to include dead states while taking cartesian product?

Answer 2

REGULAR EXPRESSION     (00+01+10+11)*(01).

further optimization could be done

Comments

do we have to include dead states whil etaking cartesian product?