Compact Normal Form for Regular Languages as Xor Automata

The only presently known normal form for a regular language L is an element of Reg is its Minimal Deterministic Automaton MDA(L). We show that a regular language is also characterized by a finite dimension dim(L), which is always smaller than the number [MDA(L)] of states, and often exponentially so. The dimension is also the minimal number of states of all Nondeterministic Xor Automaton (NXA) which accept the language. NXAs combine the advantages of deterministic automata (normal form, negation, minimization, equivalence of states, accessibility) and of nondeterministic ones (compactness, mirror language). We present an algorithmic construction of the Minimal Non Deterministic Xor Automaton MXA(L), in cubic time from any NXA for L is an element of Reg. The MXA provides another normal form: L = L' double left right arrow MXA(L) = MXA(L'). Our algorithm establishes a missing connection between Brzozowski's mirror-based minimization method for deterministic automata, and algorithms based on state-equivalence.