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)).

Playground

Benchmark

BenchmarkMinimize

goos: linux
goarch: amd64
pkg: github.com/acomagu/mindfa
BenchmarkMinimize-8         1172            933586 ns/op            6869 B/op          8 allocs/op