Nondeterministic Finite Automata
COMP1600 / COMP6260
Australian National University
Semester 2, 2021
DFA Minimisation
Elimination of equivalent states.
if two states are equivalent, one can be eliminated
Elimination of Unreachable States
if a state cannot be reached from the initial state then it can also be eliminated.
Example. S not reachable ?0
3 1-0
– S0 S1 1
6
A6: 1
0
– S 3
1/40
The Standard Minimisation Algorithm
Main Idea.
aggregate states into groups (of possibly equivalent states) initially, all states are possibly equivalent
split a group of possibly equivalent states if we have evidence that they are not equivalent.
a non-final state is never equivalent to a final state
two states are non-equivalent if the transition function takes them into
different groups (with the same letter) repeat until no more groups can be split.
Realisation.
The working data structure for the algorithm is a list of lists (“groups”) of states
On each iteration, we test one of the groups with a symbol from the alphabet.
If we notice differing behaviour, we split the group.
2/40
The Algorithm Details
Input: A list containing two “groups”. (a group is represented as a list of states). One group consists of the Final states and the other consists of the non-final states.
Data: The working data structure, WDS : [[State]], is a list of groups of states. When two states are in different groups, we know they are not equivalent.
Loop: Pick a group, {s1, …sj } and a symbol, x.
If the states {N(si,x) | i = 1,…,j} are all in the same group, then the group {s1 , …sj } is not split.
If the states {N(si,x) | i = 1,…,j} belong to different groups of WDS, then the group {s1, …sj } should be split accordingly.
Continue until we cannot, by any choice of letter, split any group.
3/40
Our Previous Example
Our running example is trivial. The initial split is it.
[[s0, s2], [s1, s3]]
?0 0 ?0 ?
10
– S0 – S1 [[s0,s2],[s1,s3]] – Sa
?0 ′
A: 6 1 [[s0,s2],[s1,s3]] A: 61 111
? ? ?
000
- S3 1 S2
[[s0,s2],[s1,s3]] 1
?
[[s0, s2], [s1, s3]]
Sb
4/40
Minimisation: Second Example
Q. What is the language of this automaton? Can you find a simpler automaton with the same language?
a ++ a S4
a
// S0 ee
b
b
b b && //
S1 a S3WW a,b
5/40
Minimisation Step by Step
a ++
<