On NFAs Where All States are Final, Initial, or Both

2008/08/18 by Jui-Yi Kao, Narad Rampersad, Kao, Jui-Yi +3
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.CC #cs.FL

paper · pdf · doi:10.48550/arxiv.0808.2417

submitted

arxiv created 2009/07/03 · arxiv updated 2009/12/01

Abstract

We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversality and inequivalence problems for these NFAs. Next, we characterize the languages accepted. Finally, we discuss some state complexity problems involving such automata.

Related

• A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata
• Incremental Construction of Compact Acyclic NFAs
• On the Complexity of Flanked Finite State Automata
• Minimal Nondeterministic Finite Automata and Atoms of Regular Languages
• Languages given by Finite Automata over the Unary Alphabet