Skip to content
/ mindfa Public

DFA minimization by Hopcroft's algorithm in Go

License

Notifications You must be signed in to change notification settings

acomagu/mindfa

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

8 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

mindfa: The implementation of Hopcroft's algorithm in Go

GoDoc

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:

DFA to be minimized.jpg
By Vevek - Own work, created with Inkscape, CC BY-SA 3.0

It results as:

Minimized DFA.jpg
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

About

DFA minimization by Hopcroft's algorithm in Go

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages