Consider the following Deterministic Finite Automation M.\n[Diagram: q0 (start/final) -0-> q0, -1-> q1. q1 -0-> q2, -1-> q0. q2 -0-> q1, -1-> q2. q1 and q2 are non-final? q0 is double circled.]\nLet $S$ denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in $S$ that are accepted by M is
- A. 0
- B. 1
- C. 2
- D. 3
Answer: C. 2
Explanation: DFA accepts strings where number of 0s is divisible by 3 (approx? check transitions).\nString structure: `x11xx11x`. 8 bits.\nPositions 2,3,6,7 are 1. $b_1 1 1 b_4 b_5 1 1 b_8$.\nBits $b_1, b_4, b_5, b_8$ can be 0 or 1.\nWe need to check which combinations of these 4 bits result in a string accepted by M.\nThe DFA sums 0s modulo 3? q0(0), q1(1), q2(2). 0 input transitions: q0->q0 (+0?), q1->q2 (+1), q2->q1 (-1?).\nActually, trace:\nq0 -0-> q0. q0 -1-> q1.\nq1 -0-> q2. q1 -1-> q0.\nq2 -0-> q1. q2 -1-> q2.\nAccepts if ends in q0.\nStrings in S have fixed 1s.\nCheck all $2^4=16$ strings? Or deduce logic.\nThis looks like 'number of 1s' mod 3? No.\nJust trace.\nKey says 2.