DFA String Examples
Construct a minimal DFA, which accepts set of all strings over {0, 1}, which when interpreted as binary number is divisible by ‘2’.
Means 110 in binary is equivalent to 6 in decimal and 6 is divisible by 2.
Answer
So if you think in the way of considering remainders if you divide by 2 that is {0, 1}
As you can see that binary number which is divisible by 2 is appearing on left state. Short Trick to create such DFAs
Create Transition Table as below
| State | 0 | 1 |
|---|---|---|
| q0 | q0 | q1 |
| q1 | q0 | q1 |
- first write the input alphabets, example 0, 1
- there will n states
- start writing states, as for n=2: q0 under 0, q1 under 1
- q0 under 0 and q1 under 1