Automaton minimization
Making a complete deterministic automaton as small as possible: unreachable states, equivalent states, separating word, Moore's partition refinement, quotient automaton and uniqueness of the minimal automaton.
- 25 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Unreachable state: what is it?
Show the answer
A state that no word can reach from the initial state.
It is removed first: it does not change the recognized language. A state other than the initial one that only has outgoing arrows is unreachable, however many it has.
This automaton has 6 states, 1 initial, 5 and 6 accepting. The starting partition is {1, 2, 3, 4} and {5, 6}. What is the partition after the first round?
```text
a b
→ 1 2 3
2 4 5
3 4 1
4 2 6
*5 2 1
*6 4 3`- {1, 3}, {2, 4}, {5, 6}
- {1, 2, 3, 4}, {5, 6}
- {1, 3, 5, 6}, {2, 4}
- {1}, {2}, {3}, {4}, {5, 6}
Show the answer
{1, 3}, {2, 4}, {5, 6}
Each state is sorted by the class of its successors by a and by b. 1 and 3 go into {1,2,3,4} by a as by b; 2 and 4 go into {5,6} by b, so they split off from 1 and 3. 5 and 6 stay together: their successors are all in the first class.
Moore's algorithm starts from the … / non-accepting partition and stops when a round no longer … the partition.
Show the answer
Moore's algorithm starts from the accepting / non-accepting partition and stops when a round no longer changes the partition.
Since each round can only split classes, and there is only a finite number of states, the algorithm always terminates.
Equivalent states: what is it?
Show the answer
Two states such that, for every word, reading it from one and from the other ends in two accepting states or in two non-accepting states.
Two equivalent states play the same role and can be merged without changing the language. They are inseparable, whatever word is read.