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

Jui-Yi Kao, Narad Rampersad, Jeffrey Shallit

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 nonuniversa…