Past exam question: 2082 Kartik (Back), Q2(b)(i)
Open in the Padhaiko appQuestion
Design a DFA with that accepts all strings containing even number of zero's and odd number of on, s.
Solution
State Definitions and Parity Invariant: The language requires tracking two independent binary parities for strings over :
- Number of zeros
- Number of ones
This yields states:
- : Even s, Even s (Start state: has zeros and ones)
- : Even s, Odd s (Accept state)
- : Odd s, Even s
- : Odd s, Odd s
Transitions:
- Reading
0toggles the zero-parity () while preserving the one-parity. - Reading
1toggles the one-parity () while preserving the zero-parity.
DFA Transition Table and Automaton Specification: The transition function is tabulated as:
| State | Input 0 | Input 1 |
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →q_ee | q_oe | q_eo |
| *q_eo | q_oo | q_ee |
| q_oe | q_ee | q_oo |
| q_oo | q_eo | q_oe |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 001
- ✓ accepts 100
- ✓ accepts 010
- ✓ accepts 111
- ✓ accepts 00111
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 11
- ✓ rejects 01
- ✓ rejects 10
- ✓ rejects 00
- ✓ rejects 000
- ✓ rejects 1100
Answer:
A 4-state DFA tracks parities with start state and unique accept state . Each input symbol toggles its corresponding coordinate.