Autor:	Brzozowski, Janusz, Tamm, Hellis
Rok vydání:	2013
Předmět:	Computer Science - Formal Languages and Automata Theory
Druh dokumentu:	Working Paper
Popis:	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. Comment: 15 pages, 29 tables
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1301.5585 Zobrazit plný text záznamu View this record from Arxiv