retagged by
1,213 views
1 votes
1 votes
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.
retagged by

1 Answer

Best answer
4 votes
4 votes
  • $\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

selected by

Related questions

1.3k
views
1 answers
1 votes
sripo asked Oct 13, 2018
1,327 views
For the given GrammarS->aA|bBA->bC|aSB->aC|bSC->aB|bA Construct DFA I am getting confused in understanding how to take the final state.
853
views
1 answers
0 votes
kumar.dilip asked Jan 19, 2019
853 views
Find the minimum number of states in the DFA which accept the language of all strings that begin or end with 00or 11.
513
views
1 answers
0 votes
Rohit Chakraborty asked Oct 5, 2023
513 views
Please explain the why A and D are correct?