1
$\begingroup$

How to design a DFA of all strings over (0,1) such that every block of 5 consecutive symbols contains at least 2 0's?

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! Did you try to solve it yourself? If so where did you get stuck? $\endgroup$ – fade2black Jul 22 '17 at 5:32
  • $\begingroup$ yeah, in order to make a state transition diagram I have listed down 7 states from q0 to q6 q0 : no. of 1s before 0 is 0, q1: no. of 1s before 0 is 1, q2: no. of 1s before 0 is 2, q3: no. of ones before 0 is 3, q4: no. of 1's before & after 0 is 1, q5: no. of 1s before 0 is 1 & after 0 is 2, q6: no. of 1s before 0 is 2 & after 0 is 1. Can't figure out how to make a transition diagram. $\endgroup$ – Pooja Jul 22 '17 at 5:53
1
$\begingroup$

The question asks HOW TO DESIGN, you don't have to write the whole DFA, but you can if you want to. Just describe how you would design.

There are 32 strings of length 5. Some of them do not contain at least two 0s, some do. Those that do not contain at least two 0s should lead to the DEAD state (from which there is no return). But those that do have at least two 0s should lead to a state that checks another block of 5 symbols.

Try to draw a binary tree of depth 5, with 0 as the left child and 1 as the right child for each node. Does it help design the DFA? For simplicity first try to design for blocks of 3 symbols not 5.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.