Let's assume we have a non-deterministic one-counter automaton without epsilon transitions. I have two questions:

  1. Is there an algorithm (if yes, what is it?) that answers whether this automaton accepts $\Sigma^*$ where $\Sigma$ is the alphabet of the automaton?

  2. 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?

  • 1
    $\begingroup$ Your first question is answered in Restricted one-counter machines with undecidable universe problems, Ibarra, O.H. Math. Systems Theory (1979) 13: 181. doi:10.1007/BF01744294. $\endgroup$ – Fabio Somenzi Apr 25 '17 at 4:57

Since a comment seems to have answered part 1 of your question, I'll tackle part 2.

Consider the language $L = \{ a^n b^n \}$. It's almost trivial to construct a one counter automaton to recognize this language; to accept $\Sigma^* - L$, switch all accepting states in the machine that accepts $L$ to rejecting, and all rejecting to accepting. This language is the classic example though of a language which cannot be recognized by a finite automata, and therefore not regular (see: pumping lemma).

  • $\begingroup$ I forgot to mention that my automata accepts by final state alone (also, just to be clear, counter cannot go below zero). $\endgroup$ – RandomDude Apr 25 '17 at 19:49
  • $\begingroup$ The restriction of accepting by final state only changes the implementation of the machine, the power remains the same. $L$ can be recognized by a one-counter machine, and not by a finite state automata. $\endgroup$ – awright96 Apr 25 '17 at 19:54
  • $\begingroup$ Could you give me an example of automaton recognizing such langauge? Maybe I'm missing something obvious, but I can't really work it out. $\endgroup$ – RandomDude Apr 25 '17 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.