<p>I summarize my comments in an answer:</p>
<p><span class="math-container">$\Sigma = \{ 0, 1, \#, Y, N\}$</span></p>
<p>Given a Turing machine <span class="math-container">$M$</span> you build a computable <span class="math-container">$f_M$</span> in this way:</p>
<p><span class="math-container">$f() = \{0\}$</span><br />
<span class="math-container">$f(0^+) = \{0,1\}$</span><br />
<span class="math-container">$f(0^w1^+) = \{1,\#\}$</span><br />
<span class="math-container">$f(0^w1^m\#)$</span> = <span class="math-container">$\{Y\}$</span> if <span class="math-container">$M(w)$</span> accepts in <span class="math-container">$m$</span> steps<br />
<span class="math-container">$f(0^w1^m\#)$</span> = <span class="math-container">$\{N\}$</span> if <span class="math-container">$M(w)$</span> rejects in <span class="math-container">$m$</span> steps<br />
<span class="math-container">$f(0^w1^m\#Y)= f(0^w1^m\#N)$</span> = <span class="math-container">$\{\bot\}$</span></p>
<p>In this way the language accepted by the auto-regressive grammar <span class="math-container">$G_{f_M}$</span> is</p>
<p><span class="math-container">$L(G_{f_M}) = \{  \langle 0^w1^m\#y \rangle \mid M(w) = y \text{ in less than m steps}\}$</span></p>
<p>So it is Turing-complete and with the above encoding can generate all the r.e. languages. I mean &quot;Turing-complete&quot; in this sense: given a Turing machine M you can build an auto-regressive grammar <span class="math-container">$G_{f_M}$</span> such that <span class="math-container">$L(G_{f_M}) \neq \emptyset$</span> if and only if <span class="math-container">$M$</span> halts.</p>
<p>Note that - if <span class="math-container">$f$</span> is recursive - the language <span class="math-container">$L(G_f)$</span> will always be recursive; i.e. it is decidable wether or not a string <span class="math-container">$x$</span> belongs to <span class="math-container">$L(G_f)$</span> (by simply building/checking all the possible &quot;generable strings&quot; up to length <span class="math-container">$|x|$</span>).</p>
<p>If <span class="math-container">$f$</span> may not halt, then things become more trivial: given a Turing machine <span class="math-container">$M$</span> build <span class="math-container">$f_M$</span> in this way:</p>
<p><span class="math-container">$f()$</span> = <span class="math-container">$\{0,1\}$</span><br />
<span class="math-container">$f( \{0,1\}^+ )$</span> = <span class="math-container">$\{ 0,1,\# \}$</span><br />
<span class="math-container">$f( w\#)$</span> = <span class="math-container">$\{\bot\}$</span> if <span class="math-container">$M(w)$</span> halts and accepts (<span class="math-container">$f$</span> simulates <span class="math-container">$M$</span> on input <span class="math-container">$w$</span>)</p>
<p>In this case <span class="math-container">$L(G_{f_M}) = \{ w\# \mid w \in L(M) \}$</span></p>

CC BY-SA 4.0
2024-09-17T13:35:39.707Z
2024-09-17T19:45:37.953Z
2024-09-17T19:45:37.953Z
Marzio De Biasi
<p><strong>Note:</strong> This answer aims to complement the accepted answer.</p>
<h3>A paradox</h3>
<p>(Claim A) The accepted answer states that auto-regressive grammars can accept, up to some encoding, all recursively enumerable languages.</p>
<p>(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.</p>
<h3>Resolution of the paradox</h3>
<p>Both claims are true. Claim A arrives at a different conclusion than claim B because it considers equivalence <strong>&quot;up to some encoding&quot;</strong>.</p>
<h4>Detailed explanation</h4>
<p>The set of recursively enumerable languages is the set of languages accepted by the class of unrestricted grammars (<a href="https://en.wikipedia.org/wiki/Unrestricted_grammar" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Unrestricted_grammar</a>). The OP (implicitly) considers a new class of grammars (like the class of auto-regressive grammars) equivalent in power iff, for a given alphabet <span class="math-container">$\Sigma$</span> and the set of terminals <span class="math-container">$\{\perp\}$</span>, the new class of grammars can accept <strong>exactly</strong> the languages that the class of unrestricted grammars can accept. In the section <strong>Edit</strong>, 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.</p>
<p>In contrast, the accepted answer considers a new class of grammars equivalent in power iff, for a given alphabet <span class="math-container">$\Sigma$</span>, there exists an alphabet <span class="math-container">$\Sigma'$</span> and a decoder <span class="math-container">$d: \Sigma'^* \rightarrow \Sigma^*$</span> such that the set <span class="math-container">$\mathcal{A} \subset \mathcal{P}(\Sigma'^*)$</span> of languages accepted by the new class of grammars can be decoded into the set  <span class="math-container">$\mathcal{A} \subset \mathcal{P}(\Sigma^*)$</span> of languages accepted by the unrestricted grammar, i.e. if we have <span class="math-container">$$\mathcal{A} = \{\{d(a') : a' \in A'\} : A' \in \mathcal{A'}\}$$</span>. 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 <span class="math-container">$d$</span>) is not defined (see also <a href="https://cs.stackexchange.com/questions/162400/how-to-formally-show-computational-equivalence-or-universality-using-encodings">https://cs.stackexchange.com/questions/162400/how-to-formally-show-computational-equivalence-or-universality-using-encodings</a>). However, the last example in the answer provides a trivial encoding that should satisfy any reasonable constraints.</p>
<h3>Summary</h3>
<p>The following table summarizes our findings:</p>
<div class="s-table-container"><table class="s-table">
<thead>
<tr>
<th>Grammar equivalence definition</th>
<th>Power</th>
</tr>
</thead>
<tbody>
<tr>
<td>exact</td>
<td>more than recursive, less than recursively enumerable</td>
</tr>
<tr>
<td>up to encoding</td>
<td>recursively enumerable</td>
</tr>
</tbody>
</table></div>
<p>In a perhaps more practically relevant scenario, we can also restrict <span class="math-container">$f$</span> to functions that <strong>must halt</strong>. In this case, the table looks as follows:</p>
<div class="s-table-container"><table class="s-table">
<thead>
<tr>
<th>Grammar equivalence definition</th>
<th>Power</th>
</tr>
</thead>
<tbody>
<tr>
<td>exact</td>
<td>recursive</td>
</tr>
<tr>
<td>up to encoding</td>
<td>recursive</td>
</tr>
</tbody>
</table></div>

CC BY-SA 4.0
2024-09-21T19:39:57.670Z
Nice! From sketch to full coherent picture! :-)
Marzio De Biasi
CC BY-SA 4.0
2024-09-21T17:34:10.193Z
2024-09-21T17:34:10.193Z
Robert Hönig
<h2>Motivation</h2>
<p>I am working on constrained decoding of large language models (LLMs).</p>
<p>Today's auto-regressive LLMs take a string <span class="math-container">$s \in \Sigma^*$</span> as input, and output a probability distribution over an alphabet <span class="math-container">$\Sigma$</span>. We then sample a symbol <span class="math-container">$\sigma$</span> from this distribution, append it to <span class="math-container">$s$</span> to construct <span class="math-container">$s' = s\cdot\sigma$</span>, and repeat the process with <span class="math-container">$s'$</span>.</p>
<p>Constrained generation restricts the output distribution to a subset <span class="math-container">$\Sigma' \subseteq \Sigma$</span>. We construct <span class="math-container">$\Sigma'$</span> as  <span class="math-container">$\Sigma' = f(s)$</span>, where <span class="math-container">$f$</span> is some computable function, and  <span class="math-container">$s$</span> is the string generated so far (auto-regressive construction).</p>
<p>I am interested in the power of the corresponding formal grammar:</p>
<ul>
<li>If we can choose any computable <span class="math-container">$f$</span> and generate strings auto-regressively, where would we find ourselves in the Chomsky hierarchy? (<em>My hunch right now is somewhere strictly between <strong>recursive</strong> and <strong>recursively enumerable</strong>.</em>)</li>
<li>Is this type of grammar already studied somewhere?</li>
</ul>
<h2>Formal question</h2>
<p>Let's define an <em>auto-regressive grammar</em> (I made up this term) as a pair <span class="math-container">$(f, \Sigma)$</span>, where</p>
<ul>
<li><span class="math-container">$\Sigma$</span> is an alphabet that includes the terminal character <span class="math-container">$\bot$</span>.</li>
<li><span class="math-container">$f: \Sigma^* \rightarrow \mathcal{P}(\Sigma)$</span> is some computable function that takes a string and returns a subset of symbols. <span class="math-container">$f$</span> may or may not halt on its input.</li>
</ul>
<p>Let <span class="math-container">$L$</span> be the language induced by <span class="math-container">$(f, \Sigma)$</span>.
A word <span class="math-container">$w = \sigma_1\cdot\sigma_1\cdot\ldots\cdot\sigma_n$</span> is in <span class="math-container">$L$</span> if we have
<span class="math-container">$$
\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})
$$</span>
and each of the invocations of <span class="math-container">$f$</span> halts.</p>
<ul>
<li>Is this a known grammar?</li>
<li>What is the power of this grammar?</li>
</ul>
<h2>My work so far</h2>
<h3>Is this a known grammar?</h3>
<p>I couldn't find it, but I also don't really know how to search for it.</p>
<h3>What is the power of this grammar?</h3>
<p>I think it is at least powerful enough to model all recursive languages (<a href="https://en.wikipedia.org/wiki/Recursive_language" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Recursive_language</a>).
To see this, note that we can just have <span class="math-container">$f(s)$</span> internally enumerate all strings in <span class="math-container">$L$</span> up until length one greater than <span class="math-container">$s$</span>, and output the delta.</p>
<p>I think it is more powerful than grammars for recursive languages, because it should be able to model the universal language (<a href="https://www.cs.columbia.edu/%7Eaho/cs3261/Lectures/L16-Universal_Language.html" rel="nofollow noreferrer">https://www.cs.columbia.edu/~aho/cs3261/Lectures/L16-Universal_Language.html</a>). To see this, note that we can model <span class="math-container">$f$</span> to accept pairs <span class="math-container">$(M, s)$</span> of a Turing machine and a string as input, and then either output <span class="math-container">$\bot$</span> if <span class="math-container">$M$</span> accepts <span class="math-container">$s$</span>, or not halt otherwise.</p>
<p>I do not know if it is as powerful as grammars for recursively enumerable languages.</p>
<p><strong>Edit:</strong> 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:</p>
<ul>
<li>We say that strings ending with a new, special symbol <span class="math-container">$\dagger$</span> should always be accepted.</li>
</ul>
<p>If we had an auto-regressive function <span class="math-container">$f$</span> to model this language, then it would have to accept <span class="math-container">$(M, s)\dagger$</span>. Thus, we need <span class="math-container">$\dagger \in f(M, s)$</span>, and <span class="math-container">$f(M, s)$</span> must halt,  for all inputs <span class="math-container">$(M, s)$</span>. But this means that <span class="math-container">$f(M, s)$</span> must <em>decide</em> if <span class="math-container">$M$</span> accepts <span class="math-container">$s$</span> [since <span class="math-container">$M$</span> accepts <span class="math-container">$s$</span> <span class="math-container">$\iff$</span> <span class="math-container">$\bot \in f(M, s)$</span>]. Hence, we could use <span class="math-container">$f$</span> to not just accept, but <em>decide</em> the universal language, which is a contradiction.</p>
<p>Does this reasoning make sense?</p>

CC BY-SA 4.0
2024-09-16T07:41:50.420Z
You can model $f: \Sigma^* \rightarrow \mathcal{P}(\Sigma)$ to incrementally "build" the string $1^m$ ("", "1", "11", "111", ...), and make it output the symbol $\bot$ if and only if the arbitrary TM $M$ halts in less than $m$ steps. In this way $L \neq \emptyset$ if and only if $M$ halts (and you can also tag the last generated string with the output of the computation). So the model can be considered Turing-complete.
Marzio De Biasi
CC BY-SA 4.0
2024-09-17T09:25:36.817Z
@Marzio interesting observation!  But to confirm, this says nothing about the power of auto-regressive grammars, i.e. it says nothing about the types of languages that auto-regressive grammars can accept?
Robert Hönig
CC BY-SA 4.0
2024-09-17T13:12:19.277Z
If it is Turing complete then it can accept all languages accepted by a Turing machine (all r.e. languages) up to some encoding. This is simply a consequence of the power that you embed in $f$ (computable). The only caveat is wether or not you allow an "input" for the regressive-grammar model. If the initial string is forced to be empty then you must somewhat build all possible inputs, then process them (adding $1^n$), and the final language using a $f_M$ can be of the form $\{ \langle 0^w,1^n,out \rangle\}$ in which $w$ is the input, and $M(w)=out$ in no more than $n$ steps
Marzio De Biasi
<fl.formal-languages><grammars>
How powerful is this "auto-regressive" grammar?
Robert Hönig
# How powerful is this "auto-regressive" grammar?

(Asked by: username_0 on 2024-09-12)

## 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](https://www.cs.columbia.edu/%7Eaho/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?

**Tags:** fl.formal-languages, grammars
> **Comments:**
> **username_1**: You can model $f: \Sigma^* \rightarrow \mathcal{P}(\Sigma)$ to incrementally "build" the string $1^m$ ("", "1", "11", "111", ...), and make it output the symbol $\bot$ if and only if the arbitrary TM $M$ halts in less than $m$ steps. In this way $L \neq \emptyset$ if and only if $M$ halts (and you can also tag the last generated string with the output of the computation). So the model can be considered Turing-complete.  
> **username_0**: @Marzio interesting observation!  But to confirm, this says nothing about the power of auto-regressive grammars, i.e. it says nothing about the types of languages that auto-regressive grammars can accept?  
> **username_1**: If it is Turing complete then it can accept all languages accepted by a Turing machine (all r.e. languages) up to some encoding. This is simply a consequence of the power that you embed in $f$ (computable). The only caveat is wether or not you allow an "input" for the regressive-grammar model. If the initial string is forced to be empty then you must somewhat build all possible inputs, then process them (adding $1^n$), and the final language using a $f_M$ can be of the form $\{ \langle 0^w,1^n,out \rangle\}$ in which $w$ is the input, and $M(w)=out$ in no more than $n$ steps  

---

## 2 answers

### Answer by username_1 on 2024-09-17. Score: 4 | Accepted answer

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 by username_0 on 2024-09-21. Score: 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 |

> **Comments:**
> **username_1**: Nice! From sketch to full coherent picture! :-)  

---

