Past exam question: 2082 Kartik (Back), Q2(c)
Open in the Padhaiko appQuestion
Minimize the given DFA.
| 0 | 1 | |
|---|---|---|
| B | C | |
| B | A | D |
| E | F | |
| E | F | |
| E | F | |
| F | F | F |
Solution
Table-Filling Algorithm Step-by-Step: The DFA has state set , start state , accept states , and non-accepting states . All states are reachable from (, , , , ).
- Initial 0-Equivalence Partition: Any accept state and non-accept state are distinguishable: pairs between and are marked. Unmarked pairs: and .
- Evaluate Unmarked Accepting Pairs :
- For all three states , on input
0they transition to , and on input1they transition to . - Hence, or , neither of which is marked.
- Thus, .
- For all three states , on input
- Evaluate Unmarked Non-Accepting Pairs :
- Pair : On input
1, (accept) while (non-accept). Since is marked, mark . - Pair : On input
1, (accept) while (non-accept). Mark . - Pair :
- On input
0: , which is unmarked. - On input
1: . But (unmarked). - Therefore, pair remains unmarked, so .
- On input
- Pair : On input
Minimized DFA Transition Table and Automaton: The equivalence classes are:
- State (Start state)
- State (Accept state)
- State (Dead state)
Minimized Transition Table:
| State | Input 0 | Input 1 |
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| *q1 | q1 | q2 |
| q2 | q2 | q2 |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 001
- ✓ accepts 10
- ✓ accepts 010
- ✓ accepts 000100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 00
- ✓ rejects 11
- ✓ rejects 011
- ✓ rejects 101
- ✓ rejects 110
Answer:
States and merge into single states. The minimal DFA has 3 states: (start), (accept), and (dead state).