Let's assume we have a non-deterministic one-counter automaton without epsilon transitions. I have two questions:
Is there an algorithm (if yes, what is it?) that answers whether this automaton accepts $\Sigma^*$ where $\Sigma$ is the alphabet of the automaton?
Let's assume that both $L$ and $\Sigma^* \setminus L$ are recognized by certain such automata. Does it mean that $L$ is regular? Why/why not?