In general, there exists NFAs of size n whose smallest equivalent DFA requires 2^n states.
But if we restrict ourselves to NFAs whose graph is eulerian, is it possible to turn any such NFA of size n into a DFA of size at most O(n) ?
If so, does it hold also for a NFAs whose graph is strongly connected ?
I would appreciate some counter example, proof or any reference to research papers dealing with this problem.
Many thanks, Luz