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.

  • $\begingroup$ 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. $\endgroup$
    – Shaull
    Sep 22 at 19:01
  • $\begingroup$ I'll state a more precise definition later today when I have the time, but yes, it must consume a symbol. $\endgroup$
    – Adalynn
    Sep 22 at 20:15
  • $\begingroup$ 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. $\endgroup$
    – Adalynn
    Sep 22 at 22:03
  • $\begingroup$ @EmilJeřábek see the newly updated version, I have added an accurate definition. $\endgroup$
    – Adalynn
    Sep 23 at 0:01
  • 1
    $\begingroup$ 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 . $\endgroup$ Sep 23 at 7:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.