3,160 views
1 votes
1 votes
Find the minimum number of states in the DFA which accept the language of all strings that begin or end with 00 or 11.
(a) 6 (b) 7
(c) 8 (d) 9

2 Answers

Best answer
6 votes
6 votes
DFA $M_1$ over {$0,1$}, that begins with $00$ or $11$ having regular expression $(00+11)(0+1)^*$

DFA $M_2$ over {$0,1$} that ends with $00$ or $11$ having regular expression $(0+1)^*(00+11)$

DFA $M$ using cross product of $M_1 \times M_2$ having start state as {$x_0,y_0$} and mark final state as any state contain $x_3$ or $y_3$ or $y_4$( and do minimization)
selected by

Related questions

4 votes
4 votes
3 answers
4
Vikrant Singh asked Jan 25, 2015
3,158 views
What is the number of states in the minimal DFA with input symbols {0,1,2} where 2nd last symbol is 1?A. 8B. 9C. 6D. None