patternMinor
Classes of languages for which the language $\{a_1^n \cdots a_k^n \mid n \geq 0\}$ is in the language for $k$ but not $k+1$
Viewed 0 times
themida_klanguagescdotsgeqbutlanguageforclasses
Problem
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)?
$$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)?
Solution
One example would be the hierarchy defined by blind counter automata.
A blind $k$-counter automaton has access to $k$ counters for which
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)$.
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)$.
Context
StackExchange Computer Science Q#82530, answer score: 4
Revisions (0)
No revisions yet.