[proofplan] Fix a type 0 grammar $G = (\Sigma, V, P, S)$. We encode entire derivations as words over the extended alphabet $\Sigma' = V \cup \Sigma \cup \{\to\}$ and exhibit $\mathcal{L}(G)$ as the projection of a computable set of word pairs. Specifically, define $Y \subseteq (\Sigma')^* \times (\Sigma')^*$ to be the set of pairs $(w, v)$ such that $v$ codes a valid $G$-derivation $S \to \sigma_1 \to \cdots \to \sigma_n = w$. A register machine can syntactically parse $v$ and check each rewriting step against the production list $P$, so $Y$ is computable. Then $w \in \mathcal{L}(G) \iff \exists v,\, (w, v) \in Y$, so $\mathcal{L}(G) = p(Y)$ is $\Sigma_1$, and hence computably enumerable by [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824). [/proofplan] [step:Fix the grammar, alphabets, and derivation conventions] Let $G = (\Sigma, V, P, S)$ be a type 0 grammar, where $\Sigma$ is the terminal alphabet (finite), $V$ is the non-terminal alphabet (finite, disjoint from $\Sigma$), $P \subseteq (V \cup \Sigma)^* \cdot V \cdot (V \cup \Sigma)^* \times (V \cup \Sigma)^*$ is a finite set of productions $\alpha \to \beta$ with $\alpha$ containing at least one non-terminal, and $S \in V$ is the start symbol. Write $N := V \cup \Sigma$ for the alphabet of sentential forms; elements of $N^*$ are strings that can appear during a derivation. The one-step derivation relation $\Rightarrow_G$ on $N^*$ is defined by: $\sigma \Rightarrow_G \tau$ iff there exist $\gamma_1, \gamma_2 \in N^*$ and a production $\alpha \to \beta \in P$ with $\sigma = \gamma_1 \alpha \gamma_2$ and $\tau = \gamma_1 \beta \gamma_2$. The language of $G$ is \begin{align*} \mathcal{L}(G) &= \{w \in \Sigma^* : S \Rightarrow_G^* w\}, \end{align*} where $\Rightarrow_G^*$ denotes the reflexive-transitive closure of $\Rightarrow_G$. Pick a symbol $\to \notin N$ (we reserve it as a separator). Define the *extended alphabet* \begin{align*} \Sigma' &:= N \cup \{\to\} = V \cup \Sigma \cup \{\to\}, \end{align*} still finite. Words over $\Sigma'$ will encode derivations. We also fix the register-machine ambient alphabet to be $\Sigma'$ augmented (if needed) so that the distinguished accept letter $a$ of the course (see Step 1 of the proof of [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824)) is present; a register machine over the course alphabet can operate on $(\Sigma')^*$ by restricting inputs appropriately. Set $\mathbb{W}' := (\Sigma')^*$ for the workspace of encoded derivations. [/step] [step:Encode derivations as words of $(\Sigma')^*$] A *derivation code* is a word $v \in \mathbb{W}'$ of the shape \begin{align*} v &= \sigma_0\, {\to}\, \sigma_1\, {\to}\, \cdots\, {\to}\, \sigma_n \end{align*} with $n \ge 0$ and each $\sigma_i \in N^* \subseteq (\Sigma')^*$. Concretely, $v$ is a derivation code iff: (i) $v$ contains only finitely many (namely exactly $n$) occurrences of $\to$; (ii) removing each $\to$ separates $v$ into $n + 1$ blocks $\sigma_0, \sigma_1, \ldots, \sigma_n$, each in $N^*$; (iii) for every $i \in \{0, 1, \ldots, n - 1\}$, $\sigma_i \Rightarrow_G \sigma_{i + 1}$ according to some production of $P$. When $v$ is a derivation code, call $\sigma_0$ its *initial string* and $\sigma_n$ its *final string*. Define \begin{align*} Y &:= \{(w, v) \in \Sigma^* \times \mathbb{W}' : v \text{ is a derivation code with initial string } S \text{ and final string } w\}. \end{align*} Every pair in $Y$ has $w \in \Sigma^*$ (the final string is required to be a terminal word), and $v \in \mathbb{W}'$. [/step] [step:Prove that $Y$ is computable] [claim:The set $Y$ is a computable subset of $\Sigma^* \times \mathbb{W}'$] We describe a total register machine $M_Y$ that, on input $(w, v)$, outputs $a$ if $(w, v) \in Y$ and $\varepsilon$ otherwise; that is, computes the indicator $\mathbb{1}_Y$. *(a) Parse $v$ into blocks.* Scan $v$ letter by letter. Maintain a list $B = (b_0, b_1, \ldots, b_k)$ of blocks, currently being written into scratch registers. Initialise with $k = 0$ and $b_0 = \varepsilon$. For each letter $\ell$ of $v$ in order: - if $\ell = \to$, increment $k$ and start a new empty block $b_k = \varepsilon$; - otherwise $\ell \in N$; append $\ell$ to the current block $b_k$ and verify $\ell \in N$ by lookup against the fixed finite set $N$ (the register machine has the elements of $V$ and $\Sigma$ hard-wired as finitely many comparison constants). If during the scan any letter $\ell$ is not in $\Sigma'$, the input is ill-formed: halt with $\varepsilon$. After the scan, we have $n := k$ and blocks $\sigma_0 = b_0, \sigma_1 = b_1, \ldots, \sigma_n = b_n \in N^*$. *(b) Check the boundary strings.* Test whether $\sigma_0 = S$ (string equality against a hard-wired constant — the single letter $S \in V$); if not, halt with $\varepsilon$. Test whether $\sigma_n = w$ (string equality against the input register holding $w$); if not, halt with $\varepsilon$. *(c) Check each rewriting step.* For each $i \in \{0, 1, \ldots, n - 1\}$, verify $\sigma_i \Rightarrow_G \sigma_{i + 1}$: for each production $\alpha \to \beta \in P$ (finitely many, hard-wired), iterate over all decompositions $\sigma_i = \gamma_1 \alpha \gamma_2$. A decomposition is determined by a starting index $j \in \{0, 1, \ldots, |\sigma_i| - |\alpha|\}$: check whether the substring of $\sigma_i$ of length $|\alpha|$ starting at position $j$ equals $\alpha$; if yes, form $\tau := \gamma_1 \beta \gamma_2$ (a finite string operation on the registers) and test $\tau = \sigma_{i + 1}$. If some $(\alpha \to \beta, j)$ witnesses the step, record success for step $i$; otherwise, after exhausting the finitely many productions and starting indices, halt with $\varepsilon$. *(d) Halt with $a$.* If all $n$ steps succeed, halt with output $a$. Each stage is a bounded loop over finite data structures (blocks, productions, starting indices, register comparisons against a fixed finite constant set), hence $M_Y$ is a total register machine. The operations used — letter-by-letter traversal, string concatenation, length computation, substring comparison against a constant — are register-machine-primitive, cf. the register machine constructions in the proof of [Recursive Implies Computable](/theorems/1817). By L0 and L1 in Step 4 of that proof (closure of total computable functions under composition and case distinction), $M_Y$ computes a total function. Its output is $a$ iff, by construction, the three conditions (i)–(iii) in Step 2 hold together with "$\sigma_0 = S$" and "$\sigma_n = w$", which is the definition of $(w, v) \in Y$. Hence $\mathbb{1}_Y$ is total computable, so $Y$ is computable. [/claim] [guided] We give the register-machine construction with more explanation of why each check is necessary and how it enforces the three clauses in the definition of "derivation code". Recall the definition: $Y = \{(w, v) : v \text{ codes a derivation } S = \sigma_0 \Rightarrow_G \cdots \Rightarrow_G \sigma_n = w\}$. To decide membership, we must check four things: (1) $v$ parses as an alternating sequence of $N^*$-blocks separated by the symbol $\to$; (2) the first block equals the single non-terminal $S$; (3) the last block equals $w$; (4) consecutive blocks are related by a single production of $P$. Why does each check terminate? Because $v$ is a finite input word: $|v| < \infty$. There are at most $|v| + 1$ blocks (each separator $\to$ introduces one additional block), the productions $P$ are a finite set (hard-wired in the machine), and for each block $\sigma_i$ there are at most $|\sigma_i| + 1$ starting indices $j$. The total work is therefore polynomial in $|v|$ and the fixed grammar size. We now describe the machine. *(a) Parse $v$ into blocks.* The machine scans $v$ letter by letter. At each position it tests whether the current letter is the separator $\to$ or one of the finitely many symbols in $V \cup \Sigma$. This test is a finite case distinction against hard-wired constants — each constant is a letter, and equality of letters is a register-machine primitive. We maintain a list of blocks in scratch registers: whenever we see $\to$, we "close" the current block and open a new one; otherwise we append the letter. What if $v$ contains a letter outside $\Sigma'$? Then the input is not a valid derivation code and the machine halts with $\varepsilon$. After the scan we have $n := k$ blocks $\sigma_0, \ldots, \sigma_n$ and we have verified clause (i) of "derivation code" implicitly (since we only accepted $\to$ as a separator and $N$-letters as block content). *(b) Check the boundary strings.* Test $\sigma_0 = S$. This is a string-equality test of $\sigma_0$ (a register content) against the single-letter constant $S$. If false, $v$ does not code a derivation from $S$, so $(w, v) \notin Y$; halt with $\varepsilon$. Test $\sigma_n = w$. String equality between two register contents, implemented by length comparison followed by pointwise letter comparison. If false, $v$ does not end with $w$; halt with $\varepsilon$. *(c) Check each rewriting step.* For each consecutive pair $(\sigma_i, \sigma_{i + 1})$, we must verify $\sigma_i \Rightarrow_G \sigma_{i + 1}$. By the definition of $\Rightarrow_G$, this means: there is a production $\alpha \to \beta \in P$ and a decomposition $\sigma_i = \gamma_1 \alpha \gamma_2$ with $\sigma_{i + 1} = \gamma_1 \beta \gamma_2$. To search for such a witness, we iterate over the finite list $P$ and, for each $\alpha \to \beta \in P$, iterate over the $|\sigma_i| - |\alpha| + 1$ possible starting positions $j$ at which $\alpha$ could sit inside $\sigma_i$ (skip if $|\alpha| > |\sigma_i|$). For each $j$, extract the substring of $\sigma_i$ of length $|\alpha|$ starting at $j$ and test equality against $\alpha$; if equal, construct $\tau = \gamma_1 \beta \gamma_2$ by concatenating the prefix of $\sigma_i$ up to $j$, then $\beta$, then the suffix from $j + |\alpha|$ onwards, and test $\tau = \sigma_{i + 1}$. If some $(\alpha \to \beta, j)$ succeeds, the $i$-th step is valid and we move on; otherwise the $i$-th step fails and we halt with $\varepsilon$. *(d) Halt with $a$.* If all $n$ steps succeed, every clause (i)–(iii) of the definition plus the boundary conditions are satisfied, so $(w, v) \in Y$; halt with $a$. Why is this a *total* register machine? Because at each stage the number of operations is bounded by a computable function of the input $|v|$ and $|w|$ and the fixed finite grammar size. The search over starting indices is a finite bounded loop; the iteration over productions is finite; the check of letter equality is a register-machine primitive. No unbounded minimisation or recursion is required. A side remark on the use of the distinguished accept letter $a$: in the course's computability framework, computable sets are those whose indicator takes values in $\{a, \varepsilon\}$. The machine $M_Y$ outputs $a$ on acceptance and $\varepsilon$ on rejection, which matches this convention. Hence $\mathbb{1}_Y : \Sigma^* \times \mathbb{W}' \to \{a, \varepsilon\}$ is total computable, and $Y$ is a computable set. [/guided] [/step] [step:Identify $\mathcal{L}(G)$ as the projection $p(Y)$ and conclude $\mathcal{L}(G) \in \Sigma_1$] By the definition of $Y$, \begin{align*} \mathcal{L}(G) &= \{w \in \Sigma^* : \exists v \in \mathbb{W}',\; (w, v) \in Y\} = p(Y). \end{align*} Indeed: $(\subseteq)$ If $w \in \mathcal{L}(G)$, there is a derivation $S = \sigma_0 \Rightarrow_G \sigma_1 \Rightarrow_G \cdots \Rightarrow_G \sigma_n = w$. Form $v := \sigma_0 {\to} \sigma_1 {\to} \cdots {\to} \sigma_n \in (\Sigma')^*$; by construction, $v$ is a derivation code with initial string $S$ and final string $w$, so $(w, v) \in Y$. $(\supseteq)$ Conversely, if $(w, v) \in Y$, then (unpacking the definition) $v = \sigma_0 {\to} \cdots {\to} \sigma_n$ with $\sigma_0 = S$, $\sigma_n = w$, and $\sigma_i \Rightarrow_G \sigma_{i + 1}$ for each $i$. Chaining, $S \Rightarrow_G^* w$, so $w \in \mathcal{L}(G)$. Therefore $\mathcal{L}(G) = p(Y)$. Since $Y$ is computable by Step 3, by the definition of $\Sigma_1$ (Step 1 of the proof of [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824)), $\mathcal{L}(G) \in \Sigma_1$. One technical remark: the definition of $\Sigma_1$ demands a computable witness $Y \subseteq \mathbb{W}^{k + 1}$ over the course's fixed ambient alphabet $\Sigma$ (not over $\Sigma'$). If $\Sigma' \supsetneq \Sigma$, we compose with a computable bijection $\beta : (\Sigma')^* \to \mathbb{W}$ (such a bijection exists and is computable because $\Sigma'$ is finite: encode each letter of $\Sigma'$ as a fixed-length block over $\Sigma$; see [Shortlex Is Order-Isomorphic to $\mathbb{N}$](/theorems/1815) for the analogous construction over $\mathbb{W}$). The image $\tilde{Y} := \{(w, \beta(v)) : (w, v) \in Y\}$ is computable because $\beta$ is a computable bijection, and $p(\tilde{Y}) = p(Y) = \mathcal{L}(G)$. Thus we may take the witness to be $\tilde{Y} \subseteq \mathbb{W}^2$, confirming $\mathcal{L}(G) \in \Sigma_1$. [/step] [step:Conclude by converting $\Sigma_1$ to computable enumerability] By Step 4, $\mathcal{L}(G) \in \Sigma_1$. By [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824), a subset of $\mathbb{W}^k$ is $\Sigma_1$ if and only if it is computably enumerable. Applied with $k = 1$ to $\mathcal{L}(G) \subseteq \mathbb{W}$, this yields: $\mathcal{L}(G)$ is computably enumerable. Since $G$ was an arbitrary type 0 grammar, every type 0 language is computably enumerable. [/step]