Problem Detail: 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 } igeq0, jgeq0, kgeq0}$ But how to prove this claim? Or is it the case that they are equivalent?
Asked By : emmy
Answered By : Hendrik Jan
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7286
