HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Is the following extension of finite state automata studied?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
studiedthefiniteautomataextensionfollowingstate

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#64113, answer score: 11

Revisions (0)

No revisions yet.