Question

Create a Deterministic finite automaton that takes in binary strings and accepts them
which has both an odd number of zeros and a sum that is divisible by
3 (but no others). For example, 0111 should be accepted, but not 011
or 111.

Answer 1

Steps:

1. Divide the above language into 2 smaller languages.
2. Design DFA for the 2 languages separately
3. Use the cross-rule to combine the 2 DFAs.

-------------------------------

1.

Split the given language into two small languages.

L1 accepts binary strings with odd 0's in it

L2 accepts binary strings with sum i.e. divisible by 3.

2.

Design the two DFAs.

3.

Use the cross-rule to find a new transition table

L1 and L2 have 2 and 4 states respectively. So our resulting DFA will have 2x4 = 8 states.

Fill the transition table for every 8 states. (It is easy. Hint: Use the transition of old DFAs)

Our start state will become q_Ac because q_A and q_c are the start state of L1 and L2 respectively.

Similarly, the final state will be q_Bf formed by q_B and q_f.

-------------------------------

Stay safe. Stay immune.

Thank you.