4
$\begingroup$

In any introductory course on the theory of computing, one encounters the language $$L_k = \{a_1^n \cdots a_k^n \mid n \geq 0\}$$ as a canonical (or at least pedagogical) counterexample for a language which is not regular ($k=2$) or context-free ($k=3$). The next jump is usually to the turing machine, where $L_k$ is in the class for all $k$.

Is there a (sensible, e.g. defined in some terms of generating grammar or recognizing automaton) hierarchy of classes of languages $\mathsf{COMP}_k$ so that $L_j \in \mathsf{COMP}_k$ for $j < k$ and $L_j \not\in \mathsf{COMP}_k$ for $j \geq k$? Ideally it would also hold generally that $\mathsf{COMP}_k \subset \mathsf{COMP}_{k+1}$. Or, perhaps, is this distinction of being able to recognize $L_k$ not important/fundamental once $k \geq 3$ (in whatever sense you want to interpret that question)?

$\endgroup$
4
$\begingroup$

One example would be the hierarchy defined by blind counter automata. A blind $k$-counter automaton has access to $k$ counters for which

  • there is an increment and a decrement instruction (and no zero-test),
  • a run is accepting if in the end, all counters are zero, and
  • during a run, the counters are allowed to be negative.

Let $\mathcal{B}_k$ denote the class of languages accepted by blind $k$-counter automata. Then $L_{k}\in \mathcal{B}_{k-1}$: while you read $a_1$'s, you increment all $k-1$ counters simultaneously; then each of the remaining $k-1$ letter blocks decreases one of the counters.

On the other hand, one has $L_{k}\notin\mathcal{B}_{k-2}$. This can be shown, for example, using Theorem 6.4 in Fernau and Stiebe's paper on valence automata/grammars. This pumping lemma allows, in a blind $\ell$-counter automaton, the simultaneous repetition of $\le\ell+1$ non-empty factors. Hence, if we had $L_k\in\mathcal{B}_{k-2}$, we could repeat $\le k-1$ factors, which can span at most $k-1$ distinct letters in a word $a_1^*\cdots a_k^*$. Hence, we could pump up powers of some $a_i$'s without touching at least one letter $a_j$, which clearly leads out of the language. In Fernau and Stiebe's paper, the class $\mathcal{B}_k$ is denoted $\mathscr{L}(\mathrm{Val},\mathrm{Reg},\mathbb{Z}^k)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.