2,653 views

2 Answers

Best answer
16 votes
16 votes

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$

selected by
–4 votes
–4 votes
REGULAR EXPRESSION     (00+01+10+11)*(01).

further optimization could be done

Related questions

1 votes
1 votes
0 answers
1
pC asked Jul 22, 2016
316 views
Construct Compound FA that accept strings Even number of a's and ODD number of B's
0 votes
0 votes
1 answer
3
Arnabi asked Jan 13, 2017
1,434 views
Construct the dfa that accepts all the strings of a's and b's where no of a's is even OR no of b's is odd.
3 votes
3 votes
1 answer
4