Home > Theory Of Computation > Construct Minimal DFA That Accepts All Strings Of 0’s & 1’s Where a) No Of 0’s Is Even b) No Of 1’s Is Odd

Construct Minimal DFA That Accepts All Strings Of 0’s & 1’s Where a) No Of 0’s Is Even b) No Of 1’s Is Odd

Construct Minimal DFA That Accepts All Strings Of 0’s & 1’s Where a) No Of 0’s Is Even b) No Of 1’s Is Odd

In This Problem, He Asked About The Characters In The String, He Didn’t Ask The Length Of String.

 

a) No 0s 0’s Is Even

In The String, The Number Of 0’s Should Be Even.

Means L={ε,00,100001,10000001,1000000001….} // 2,4,6,8 Strings Which Are Even.

Zero Length=Even

ε=Intial & Final State

 

 

Here ε Is Even, So qIs My Initial & Final State.

If I Get A Single Zero On q0, I’ll Go To q1(non-final states)

If I Get 00 I’ll Come To Final State ‘q0

If I Get Odd Number Of Zero’s I’ll Go To Non-Final (q1), If I Get Even Number Of 0’s I’ll Come To Final State(q0)

 

FINAL DFA

b) No Of 0’s Is Odd (I’ll Get 1,3,5,7,9 Odd No Of Zero’s In String, I’ll Accept)

L={0,0001,010101010,……}

 

One thought on “Construct Minimal DFA That Accepts All Strings Of 0’s & 1’s Where a) No Of 0’s Is Even b) No Of 1’s Is Odd

Leave a Reply

Secured By miniOrange