1.05K viewsTOC
0
0 Comments

Construct a DFA to accept all strings(0+1)* with an equal number of zeros and ones such that each prefix has at most one more zero than ones and at most one more one than zeros.

0
Anonymous 0 Comments

i think the strings in this question will be of the form 0101 or 1010 or 0110 i.e alternating between 0s and 1s .. if i have 0011 then whn i take 00 as substring thn it will voilate my condition(2 0s and no 1s)as i can have atmost one more zero than 1s but here i have 2 1s.difference between 0s and 1s in any prefix should be atmost 1.

So a DFA can be created using these 2 type of strings..

WP2Social Auto Publish Powered By : XYZScripts.com