test book

Question

The minimum number of states required to contruct a DFA accepting languages L= { w | w has an even number of both 0's and 2 's , and an odd number of 1's  } over the alphabet $\Sigma =\left \{ 0,1,2,3 \right \}$ is _____

 

please write regular expression also.

Comments

all are AND conditions

---

@debashish i think so...that why it is time waste question...

---

how many states required for NFA?

Answer 1

• $\text{ let } \;\; x = n_0(w) \;\; \text{and}\;\; y = n_1(w) \;\; \text{and}\;\; z = n_2(w) ..$
• Values of x,y,z cab be odd or even, two possibilities.

Now if we label our states according to these possibilities then 8 distinct states are coming. 

• odd = $1$ even = $0$
• state $000$ means even $0$'s and even $1$'s and even $2$'s
• state $110$ means odd $0$'s and odd $1$'s and even $2$'s
• state $111$ means odd $0$'s and odd $1$'s and odd $2$'s
• etc...

$010$ is the final state

Comments

could have mentioned what are  final states

---

@debashish right..

---

@debashish i dont think we can minimise no of state even if we do it with NFA

---

Debashish Deka  very clearly and very nicely explained with great patience