Problem Detail: Consider a finite state machine as usual, but every transition, it can also update an integer counter by adding or subtracting a number. Say, a transition function of the form $delta(q,a) = (p,k)$ moves to the new state $p$, and add $k$ to the counter, where $k in mathbb{Z}$ (so $k$ can be positive, negative, or zero). A string is accepted if the final state and the counter value is in $F$, where $F$ is a finite set of pairs of states and counter values. Is this model known? I could not find any reference of this particular extension.
Asked By : Chao Xu
Answered By : Hendrik Jan
Assuming $k$ can be any integer, then this can be formalized as a blind one-counter automaton. Usually these automata accept on final state when its counter is zero, but we can easily model your acceptance type if you allow $epsilon$ transitions (that do not consume input). If I am not mistaken, like with finite state automata, one can get rid of the $epsilon$, but that is a non-trivial result. There are several types of one-counter automata. In the most general form they are allowed to test whether the value of the counter equals zero. The languages they accept are a strict subset of the context-free languages. The model you are probably looking for is called blind, it cannot test for zero, except as the final test for acceptance at the end of the computation.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/64113 Ask a Question Download Related Notes/Documents
