Past exam question: 2082 Chaitra (Regular), Q4
Open in the Padhaiko appDesign a DFA over that can recognize the string containing number of 1 multiple of 3 and number of 0 multiple of 2. Check your design for .
Solution
State Representation and Invariant: The condition requires simultaneously tracking:
- The count of s modulo : .
- The count of s modulo : .
We define states where and :
- : mod , mod (Start state and unique Accept state)
- : mod , mod
- : mod , mod
- : mod , mod
- : mod , mod
- : mod , mod
Transition Function:
- On input :
- On input :
Transition Table and Automaton Specification: The formal transition table for DFA is:
| State | Input 0 | Input 1 |
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →*q00 | q10 | q01 |
| q01 | q11 | q02 |
| q02 | q12 | q00 |
| q10 | q00 | q11 |
| q11 | q01 | q12 |
| q12 | q02 | q10 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 00
- ✓ accepts 111
- ✓ accepts 00111
- ✓ accepts 1010111001
- ✓ accepts 11100
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 01
- ✓ rejects 10
- ✓ rejects 11
- ✓ rejects 000
- ✓ rejects 1010
Verification Trace for Given String w = 1010111001: Given string has length :
- Total count of s: (indices ), and .
- Total count of s: (indices ), and .
Since both modulo constraints are satisfied, must be accepted.
Trace of state transitions:
The final state is , so the string is correctly accepted.
The 6-state DFA tracking accepts strings ending in state . For , the machine processes all 10 symbols and terminates in accepting state , confirming that is accepted.