How powerful is this "auto-regressive" grammar?

Question

Motivation

I am working on constrained decoding of large language models (LLMs).

Today's auto-regressive LLMs take a string $s \in \Sigma^*$ as input, and output a probability distribution over an alphabet $\Sigma$. We then sample a symbol $\sigma$ from this distribution, append it to $s$ to construct $s' = s\cdot\sigma$, and repeat the process with $s'$.

Constrained generation restricts the output distribution to a subset $\Sigma' \subseteq \Sigma$. We construct $\Sigma'$ as $\Sigma' = f(s)$, where $f$ is some computable function, and $s$ is the string generated so far (auto-regressive construction).

I am interested in the power of the corresponding formal grammar:

• If we can choose any computable $f$ and generate strings auto-regressively, where would we find ourselves in the Chomsky hierarchy? (My hunch right now is somewhere strictly between recursive and recursively enumerable.)
• Is this type of grammar already studied somewhere?

Formal question

Let's define an auto-regressive grammar (I made up this term) as a pair $(f, \Sigma)$, where

• $\Sigma$ is an alphabet that includes the terminal character $\bot$.
• $f: \Sigma^* \rightarrow \mathcal{P}(\Sigma)$ is some computable function that takes a string and returns a subset of symbols. $f$ may or may not halt on its input.

Let $L$ be the language induced by $(f, \Sigma)$. A word $w = \sigma_1\cdot\sigma_1\cdot\ldots\cdot\sigma_n$ is in $L$ if we have $$ \sigma_1 \in f() \\ \sigma_2 \in f(\sigma_1) \\ \sigma_3 \in f(\sigma_1 \cdot \sigma_2) \\ \ldots \\ \sigma_n \in f(\sigma_1\cdot\sigma_1\cdot\ldots\cdot\sigma_{n-1}) \\ \bot \in f(\sigma_1\cdot\sigma_1\cdot\ldots\cdot\sigma_{n}) $$ and each of the invocations of $f$ halts.

• Is this a known grammar?
• What is the power of this grammar?

My work so far

Is this a known grammar?

I couldn't find it, but I also don't really know how to search for it.

What is the power of this grammar?

I think it is at least powerful enough to model all recursive languages (https://en.wikipedia.org/wiki/Recursive_language). To see this, note that we can just have $f(s)$ internally enumerate all strings in $L$ up until length one greater than $s$, and output the delta.

I think it is more powerful than grammars for recursive languages, because it should be able to model the universal language (https://www.cs.columbia.edu/~aho/cs3261/Lectures/L16-Universal_Language.html). To see this, note that we can model $f$ to accept pairs $(M, s)$ of a Turing machine and a string as input, and then either output $\bot$ if $M$ accepts $s$, or not halt otherwise.

I do not know if it is as powerful as grammars for recursively enumerable languages.

Edit: I think now that it is less powerful than grammars for recursively enumerable languages. To see this, consider again that it should be able to model the universal language. But this time, we make the following modification to the universal language:

• We say that strings ending with a new, special symbol $\dagger$ should always be accepted.

If we had an auto-regressive function $f$ to model this language, then it would have to accept $(M, s)\dagger$. Thus, we need $\dagger \in f(M, s)$, and $f(M, s)$ must halt, for all inputs $(M, s)$. But this means that $f(M, s)$ must decide if $M$ accepts $s$ [since $M$ accepts $s$ $\iff$ $\bot \in f(M, s)$]. Hence, we could use $f$ to not just accept, but decide the universal language, which is a contradiction.

Does this reasoning make sense?

Answer 1

I summarize my comments in an answer:

$\Sigma = \{ 0, 1, \#, Y, N\}$

Given a Turing machine $M$ you build a computable $f_M$ in this way:

$f() = \{0\}$
$f(0^+) = \{0,1\}$
$f(0^w1^+) = \{1,\#\}$
$f(0^w1^m\#)$ = $\{Y\}$ if $M(w)$ accepts in $m$ steps
$f(0^w1^m\#)$ = $\{N\}$ if $M(w)$ rejects in $m$ steps
$f(0^w1^m\#Y)= f(0^w1^m\#N)$ = $\{\bot\}$

In this way the language accepted by the auto-regressive grammar $G_{f_M}$ is

$L(G_{f_M}) = \{ \langle 0^w1^m\#y \rangle \mid M(w) = y \text{ in less than m steps}\}$

So it is Turing-complete and with the above encoding can generate all the r.e. languages. I mean "Turing-complete" in this sense: given a Turing machine M you can build an auto-regressive grammar $G_{f_M}$ such that $L(G_{f_M}) \neq \emptyset$ if and only if $M$ halts.

Note that - if $f$ is recursive - the language $L(G_f)$ will always be recursive; i.e. it is decidable wether or not a string $x$ belongs to $L(G_f)$ (by simply building/checking all the possible "generable strings" up to length $|x|$).

If $f$ may not halt, then things become more trivial: given a Turing machine $M$ build $f_M$ in this way:

$f()$ = $\{0,1\}$
$f( \{0,1\}^+ )$ = $\{ 0,1,\# \}$
$f( w\#)$ = $\{\bot\}$ if $M(w)$ halts and accepts ($f$ simulates $M$ on input $w$)

In this case $L(G_{f_M}) = \{ w\# \mid w \in L(M) \}$

Answer 2

Note: This answer aims to complement the accepted answer.

A paradox

(Claim A) The accepted answer states that auto-regressive grammars can accept, up to some encoding, all recursively enumerable languages.

(Claim B) In a seeming contradiction, the OP presents an example of a recursively enumerable language that cannot be accepted by any auto-regressive grammar.

Resolution of the paradox

Both claims are true. Claim A arrives at a different conclusion than claim B because it considers equivalence "up to some encoding".

Detailed explanation

The set of recursively enumerable languages is the set of languages accepted by the class of unrestricted grammars (https://en.wikipedia.org/wiki/Unrestricted_grammar). The OP (implicitly) considers a new class of grammars (like the class of auto-regressive grammars) equivalent in power iff, for a given alphabet $\Sigma$ and the set of terminals $\{\perp\}$, the new class of grammars can accept exactly the languages that the class of unrestricted grammars can accept. In the section Edit, the OP describes a language for which this is not the case, and concludes that the class of auto-regressive grammars is less powerful than unrestricted grammars.

In contrast, the accepted answer considers a new class of grammars equivalent in power iff, for a given alphabet $\Sigma$, there exists an alphabet $\Sigma'$ and a decoder $d: \Sigma'^* \rightarrow \Sigma^*$ such that the set $\mathcal{A} \subset \mathcal{P}(\Sigma'^*)$ of languages accepted by the new class of grammars can be decoded into the set $\mathcal{A} \subset \mathcal{P}(\Sigma^*)$ of languages accepted by the unrestricted grammar, i.e. if we have $$\mathcal{A} = \{\{d(a') : a' \in A'\} : A' \in \mathcal{A'}\}$$. The accepted answer gives encodings that show this is the case. One issue with this equivalence definition is that the allowed complexity of encodings (i.e. the power of $d$) is not defined (see also https://cs.stackexchange.com/questions/162400/how-to-formally-show-computational-equivalence-or-universality-using-encodings). However, the last example in the answer provides a trivial encoding that should satisfy any reasonable constraints.

Summary

The following table summarizes our findings:

Grammar equivalence definition	Power
exact	more than recursive, less than recursively enumerable
up to encoding	recursively enumerable

In a perhaps more practically relevant scenario, we can also restrict $f$ to functions that must halt. In this case, the table looks as follows:

Grammar equivalence definition	Power
exact	recursive
up to encoding	recursive