5
$\begingroup$

This language I think is not accepted by a deterministic one counter but accepted by a non-deterministic one counter :

$L = \{a^{i}b^{j}c^{k} \mid (i=j) \vee (j=k) \text{ such that } i\geq0, j\geq0, k\geq0\}$

But how to prove this claim?

Or is it the case that they are equivalent?

|cite|improve this question
$\endgroup$
2
$\begingroup$

You are right: the language $L$ from your question is accepted by a (nondeterministic) one-counter automaton.

Now for the deterministic case. Counter automata are a special case of push-down automata, where one only uses a single stack symbol (apart from a bottom-of-stack). Every (deterministic) one-counter language is also a (deterministic) push-down language. So in order to demonstrate it is not a deterministic one-counter language, I show a stronger result: it is even not accepted by a deterministic PDA.

According to Ogden, in his paper introducing Ogden's Lemma, that same language $L$ is inherently ambiguous context-free, meaning that every possible context-free grammar for the language is ambiguous, i.e., it has a string with two different succesful derivation trees. On the other hand, it is known that every deterministic PDA can be transformed into a non-ambiguous CFG. In fact I believe the standard construction PDA to CFG does the trick (but that is not obvious). Hence as there is no non-ambiguous CF grammar for $L$ (Ogden), there can be no deterministic PDA for $L$, and in particular no deterministic one-counter automaton.

Conclusion: for one-counter automata determinism is less powerful than the general model, using your example.

(In an edit I moved info from comments into this text.) Reference, see also Wikipedia: Ogden, W. (1968). A helpful result for proving inherent ambiguity. Math. Syst. Theory 2, 191–194.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Which is that example? the example I found was the following cstheory.stackexchange.com/questions/9673/… palindrome cannot be recognized by pda with one stack symbol; be it non deterministic. $\endgroup$ – e_noether Dec 10 '12 at 13:50
  • $\begingroup$ I think you need to be more elaborate. The second paragraph is misleading in particular: finite automata are a special case of PDA, too, but there nondeterminism is not more powerful. $\endgroup$ – Raphael♦ Dec 11 '12 at 0:20
  • $\begingroup$ thank you HendricJan that was helpful. Can you point me to the paper that you are referring to? $\endgroup$ – e_noether Dec 11 '12 at 11:56
  • $\begingroup$ I am glad I could help you a little here. The full reference is added to the main answer, see also the wikipedia lemma. $\endgroup$ – Hendrik Jan Dec 11 '12 at 21:44
-4
$\begingroup$

All non-deterministic finite-state automata (NFA) can be represented with an equivalent deterministic finite-state automata (DFA). If you can make a NFSA that recognizes the language, you can convert it to a DFA. Have a look here for more information on how to do that.

In this particular case, I believe that that language cannot be represented even by a NFA, as it would require an infinite number of states to represent the different values of i, j and k (as FSA do not have "memory" so a machine cannot remember that it's counted i a's to count that many b's).

|cite|improve this answer
$\endgroup$
  • 5
    $\begingroup$ The question is about one counter automata. NFA + a counter. There are finite no of states and on each transition the counter value can be incremented, decremented or checked for zero $\endgroup$ – e_noether Dec 10 '12 at 6:58

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.