Minimization of unary symmetric difference NFAs
Lynette van Zijl, Graham Müller · South African Institute of Computer Scientists and Information Technologists · 2004
We investigate the minimization of unary symmetric difference nondeterministic finite automata. To this end, we develop a modification of the Berlekamp-Massey algorithm. We then prove that, given a unary symmetric difference nondeterministic finite automaton with one final state, this modified algorithm produces a minimal symmetric difference nondeterministic finite automaton which accepts the same language. We also discuss the application of the technique in the case where the nondeterministic finite automaton has more than one final state.