2013/01/23 by Janusz Brzozowski, Brzozowski, Janusz, Hellis Tamm +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL
paper · pdf · doi:10.48550/arxiv.1301.5585
15 pages, 29 tables
arxiv created 2013/01/23 · arxiv updated 2013/01/24
We examine the NFA minimization problem in terms of atomic NFA's, that is, NFA's in which the right language of every state is a union of atoms, where the atoms of a regular language are non-empty intersections of complemented and uncomplemented left quotients of the language. We characterize all reduced atomic NFA's of a given language, that is, those NFA's that have no equivalent states. Using atomic NFA's, we formalize Sengoku's approach to NFA minimization and prove that his method fails to find all minimal NFA's. We also formulate the Kameda-Weiner NFA minimization in terms of quotients and atoms.