# Languages recognized Counter DFA

I just randomly started fooling around with formal languages, grammars, and machines, and I have an extension to DFAs that I do not know what the class of languages it can recognize is.

I'll give a formal definition below.

Let's define this $$n$$-counter DFA as a 5-tuple, similar to a normal DFA $$M = (Q, \Sigma, \eta : Q \times \mathcal{P}(I_n) \times \Sigma \to Q \times \mathbb{Z}^n, q_0 \in Q, F \subseteq Q)$$ Where $$I_n = \{1, \cdots, n\}$$, and $$\mathcal{P}$$ denotes the power set.

For ease of reference, let us say that $$\eta(q, z, s) \equiv (\eta_q(q, z, s), \eta_c(q, z, s))$$, defined in the natural way.

Let us call a configuration of $$M$$ as a member of $$C = Q \times \mathbb{Z}^n$$. From here, let us define the actual transition function, $$\delta : C \times \Sigma \to C$$, in terms of $$\eta$$: $$\delta( (q, c) \in C, s \in \Sigma ) := (\eta_q(q,\{i\in I_n|c_i = 0\},s), \\c+\eta_c(q, \{i \in I_n|c_i=0\},s))$$

With addition on tuples being defined element-wise, and members of tuples being accessed by subscripts, and 1-indexed.

Similarly let us extend this transition function to a $$\delta^\ast : C \times \Sigma^\ast\to C$$ as follows: $$\delta^\ast((q, c) \in C, \varepsilon \in \Sigma^\ast) := (q, c) \\ \delta^\ast((q, c) \in C, \langle s \rangle \in \Sigma^\ast) := \delta((q, c), s) \forall s \in \Sigma\\ \delta^\ast((q, c) \in C, sx \in \Sigma^\ast) := \delta^\ast(\delta((q, c), s), x) \forall s \in \Sigma, x \in \Sigma^\ast$$ And as well define our initial configuration as $$C_0 := (q_0, \langle 0, \cdots, 0\rangle \in \mathbb{Z}^n)$$, and define whether a string $$s$$ is accepted as: $$s \in L(M) \Leftrightarrow \delta^\ast(C_0, s) \in F \times \{\langle 0, \cdots, 0 \rangle\}$$

I've constructed a few of these $$n$$-counter DFAs that can recognize a wide variety of languages from different levels in the Chomsky hierarchy, such as $$\{0^n1^n | n \geq 1\} \\ \{0^n1^n2^n | n \geq 1\} \\ \{a^mb^nc^md^n | m, n \geq 0\} \\ \{(ab^n)^n | n \geq 0\}$$ (That last one I need to double-check, but I think my construction works)

I've noticed that the forced consumption of a symbol per transition vastly cripples the machine, as if we were to allow $$\epsilon$$-transitions, I am fairly sure that a n-counter DFA with $$\epsilon$$-transitions is able to simulate a n-register Minsky machine with $$n$$ registers fairly directly, so we have TCness past a point.

I was wondering whether this class of languages had been investigated in some form before, I know that something similar, albeit with only $$n=1$$. and $$\epsilon$$-transitions being allowed, has been worked on a bit.

• This is not precisely a counter machine, because the 0-tests are only at the end. But it is a well-studied variant, see e.g., Vector Addition Systems, Counter Automata, Minsky Machines. Sep 22 at 19:01
• I'll state a more precise definition later today when I have the time, but yes, it must consume a symbol. Sep 22 at 20:15
• Alright, edited to add a more formalized specification, and some motivating examples that led me to question why I have a construction for $(ab^n)^n$, but not something as simple as a palindrome. Sep 22 at 22:03
• @EmilJeřábek see the newly updated version, I have added an accurate definition. Sep 23 at 0:01
• Thank you. I removed my comments that are no longer relevant. As an upper bound, languages accepted by counter DFA are computable in one-way logspace (1L), as studied in epubs.siam.org/doi/10.1137/0210027 . Sep 23 at 7:43