mindfa: The implementation of Hopcroft's algorithm in Go
The implementation of DFA minimization using Hopcroft's algorithm in Go. The time complexity is O(n log n) and the memory complexity is O(n)(n is the number of the states of the input DFA).
Example Usage
Consider minimizing this DFA:
By Vevek - Own work, created with Inkscape, CC BY-SA 3.0
It results as:
By Vevek - Own work, created with Inkscape, CC BY-SA 3.0
nState := 6
nSymbol := 2
finals := []int{2, 3, 4}
transitions := [][]int{
// 0 1
0: {1, 2}, // a
1: {0, 3}, // b
2: {4, 5}, // c
3: {4, 5}, // d
4: {4, 5}, // e
5: {5, 5}, // f
}
transitionFunc := func(state, symbol int) int { return transitions[state][symbol] }
partitions := mindfa.Minimize(nState, nSymbol, finals, transitionFunc)
fmt.Println(partitions)Output:
[[2 3 4] [0 1] [5]]
(means (c, d, e), (a, b), (f)).
Benchmark
goos: linux
goarch: amd64
pkg: github.com/acomagu/mindfa
BenchmarkMinimize-8 1172 933586 ns/op 6869 B/op 8 allocs/op