Theory of computaion

Question

Minimum number of states in DFA over Ʃ = {0, 1} with each string contains odd number of 0’s or odd number of 1’s.

(a) 3 (b) 4 (c) 5 (d) 6

Can anyone draw the Dfa? :{

Comments

b) 4

---

remember For AND , OR (it could be mod or odd even)is ask in the question between any language {0,1,2.....}  ,{a,b...}

GRID like structure is used  

Answer 1

4 states

Answer 2

A good question,

Key point is "each string contains odd number of 0’s or odd number of 1’s"

Here, or used, that means any one from both or both conditions.

You can solve directly as @M K utkarsh solved or u can solve using complement method.

Let's say; A= Odd no. of 0's    B= Odd no. of 1's

So,  L= A+B

Then, L'(complement of L)= (A+B)' = A'B'   ( A': not odd no. of 0s = even no. of 0s)

 we can say that, Even no. of 0s AND Even no. of 1s(Actually with AND we can easily draw DFA)

DFA :

Now, Complement of a DFA is , 

Convert Non-final states with final states( Non-final states <--> final states)

And you'll get your final DFA.

PS: for such type questions, even/odd no. of 0s and/or even/odd no. of 1s

no. of States in DFA is 4.

You can make combinations and check.  

for further info:

ref: https://www.geeksforgeeks.org/dfa-machines-accepting-odd-number-of-0s-or-and-even-number-of-1s/