[proofplan] We establish a bijective correspondence between $G$-derivations from $S$ and *derivative sequences* of parse trees that start from the one-node tree labelled $S$. Applying a production at a chosen position in a derivation corresponds to expanding the corresponding leaf in a parse tree. Under this bijection, the yield $\sigma_{\mathbb{T}}$ of the final tree equals the derived word. The forward direction ($w \in \mathcal{L}(G) \Rightarrow$ parse tree exists) extracts a derivative sequence from a derivation and takes its final tree. The reverse direction (parse tree $\Rightarrow w \in \mathcal{L}(G)$) reads off a derivation by iteratively expanding leaves of the tree; termination is guaranteed because the tree is finite, and the expansion schedule (shallowest unexpanded variable leaf first) gives a well-defined algorithm producing $S \xrightarrow{*}_G w$. [/proofplan] [step:Fix notation for grammars, derivations, and parse trees] Let $G = (V, \Sigma, P, S)$ be a [context-free grammar](/pages/???), with disjoint finite sets $V$ (variables) and $\Sigma$ (terminals), start variable $S \in V$, and production set $P \subseteq V \times (V \cup \Sigma)^*$; a production is written $A \to \gamma$. A *sentential form* is an element of $(V \cup \Sigma)^*$. A one-step derivation \begin{align*} \alpha \Rightarrow_G \beta \end{align*} holds iff $\alpha = \mu A \nu$ and $\beta = \mu \gamma \nu$ for some $\mu, \nu \in (V \cup \Sigma)^*$ and some production $A \to \gamma$; a *derivation* $S \xrightarrow{*}_G w$ is a finite chain $S = \alpha_0 \Rightarrow_G \alpha_1 \Rightarrow_G \cdots \Rightarrow_G \alpha_n = w$ with $w \in \Sigma^*$. Define $\mathcal{L}(G) := \{w \in \Sigma^* : S \xrightarrow{*}_G w\}$. A *$G$-parse tree* is a finite rooted tree $\mathbb{T} = (T, \ell)$ whose node set $T \subset \mathbb{N}^*$ is prefix-closed and closed under "younger siblings" (if $ti \in T$ and $0 \le j < i$ then $tj \in T$), with labelling \begin{align*} \ell: T \to V \cup \Sigma \cup \{\varepsilon\}, \end{align*} subject to: - internal nodes (those with at least one child) carry labels in $V$; - leaves may carry labels in $\Sigma \cup \{\varepsilon\}$ (terminal/epsilon leaves) or in $V$ (variable leaves, only in non-final intermediate trees); - if $t$ has children $t0, t1, \dots, tn$ and $\ell(t) = A$, then $A \to \ell(t0)\ell(t1)\cdots \ell(tn)$ is a production in $P$ (reading child labels left to right and interpreting $\varepsilon$-labels as the empty string yields the right-hand side). The *yield* of $\mathbb{T}$ is \begin{align*} \sigma_\mathbb{T} \in \Sigma^*, \end{align*} defined as the concatenation of the leaf labels read in left-to-right (depth-first) order, treating $\varepsilon$-labels as the empty string. A parse tree is *complete* iff every leaf has label in $\Sigma \cup \{\varepsilon\}$; we want to show $w \in \mathcal{L}(G)$ iff there is a complete parse tree with root label $S$ and yield $w$. [/step] [step:Define derivative sequences of parse trees] A *derivative sequence* (of length $n$) is a sequence $(\mathbb{T}_i)_{i=0}^n$ of parse trees with: - $\mathbb{T}_0 = (\{\varepsilon\}, \ell_0)$ with $\ell_0(\varepsilon) = S$ (the single-node tree labelled $S$); - for every $0 \le i < n$, the tree $\mathbb{T}_{i+1}$ is obtained from $\mathbb{T}_i$ by *expanding a variable leaf*: choose a leaf $t \in T_i$ with $\ell_i(t) = A \in V$ and a production $A \to x_0 x_1 \cdots x_k \in P$ (with $x_j \in V \cup \Sigma \cup \{\varepsilon\}$), then form $\mathbb{T}_{i+1}$ by setting \begin{align*} T_{i+1} &:= T_i \cup \{t0, t1, \dots, tk\}, \\ \ell_{i+1}(s) &:= \begin{cases} \ell_i(s), & s \in T_i \\ x_j, & s = tj,\ 0 \le j \le k. \end{cases} \end{align*} The final tree $\mathbb{T}_n$ of a derivative sequence need not be complete, but $w \in \Sigma^*$ corresponds to sequences ending in a complete tree with yield $w$. [/step] [step:Construct the bijection between $G$-derivations and derivative sequences] [claim:There is a length-preserving bijection between $G$-derivations $S \xrightarrow{*}_G w$ and derivative sequences $(\mathbb{T}_i)_{i=0}^n$ with $\mathbb{T}_n$ complete and $\sigma_{\mathbb{T}_n} = w$] We build maps in both directions and check they are inverse. *Derivation to sequence.* Given a derivation $S = \alpha_0 \Rightarrow_G \alpha_1 \Rightarrow_G \cdots \Rightarrow_G \alpha_n = w$, we inductively construct trees $(\mathbb{T}_i)_{i=0}^n$ maintaining the invariant: reading the leaves of $\mathbb{T}_i$ in left-to-right order yields $\alpha_i$ (terminal or variable symbols, $\varepsilon$-leaves absorbed). Set $\mathbb{T}_0$ to be the one-node tree labelled $S$; the invariant holds because $\alpha_0 = S$. For the inductive step, the step $\alpha_i \Rightarrow_G \alpha_{i+1}$ rewrites the $k$-th symbol of $\alpha_i$ (for some well-defined $k$) using a production $A \to x_0 \cdots x_m$; the $k$-th leaf of $\mathbb{T}_i$ in left-to-right order is a variable leaf with label $A$ (by the invariant), so we expand it with that production, obtaining $\mathbb{T}_{i+1}$; the new leaf sequence is precisely $\alpha_{i+1}$. Because $\alpha_n = w \in \Sigma^*$, the final tree $\mathbb{T}_n$ has all leaves in $\Sigma \cup \{\varepsilon\}$ and yield $w$. *Sequence to derivation.* Given a derivative sequence $(\mathbb{T}_i)_{i=0}^n$ with final tree complete and yield $w$, set $\alpha_i$ to be the concatenation of leaf labels of $\mathbb{T}_i$ read left-to-right (with $\varepsilon$-labels absorbed). Then $\alpha_0 = S$ (single leaf), $\alpha_n = \sigma_{\mathbb{T}_n} = w$ (complete tree), and each transition $\mathbb{T}_i \to \mathbb{T}_{i+1}$ (expand leaf $t$ with label $A$ and production $A \to x_0 \cdots x_m$) replaces one $A$ in $\alpha_i$ by $x_0 \cdots x_m$, which is exactly a one-step derivation $\alpha_i \Rightarrow_G \alpha_{i+1}$. *Mutual inversion.* Both maps are deterministic given the data (each preserves the record of which leaf/symbol is expanded and which production is used); applying one after the other recovers the original data. Hence the maps are mutually inverse. [/claim] [/step] [step:Forward direction — from $w \in \mathcal{L}(G)$ construct a parse tree with yield $w$] Assume $w \in \mathcal{L}(G)$, so there exists a derivation $S = \alpha_0 \Rightarrow_G \cdots \Rightarrow_G \alpha_n = w$. By the previous step, we obtain a derivative sequence $(\mathbb{T}_i)_{i=0}^n$ whose final tree $\mathbb{T}_n$ is complete with yield $\sigma_{\mathbb{T}_n} = w$ and root label $S$. Take $\mathbb{T} := \mathbb{T}_n$; this is a $G$-parse tree starting from $S$ with yield $w$. [/step] [step:Reverse direction — from a parse tree with yield $w$ construct a derivation] Let $\mathbb{T}$ be a complete $G$-parse tree with root label $S$ and $\sigma_\mathbb{T} = w$. We construct a derivative sequence $(\mathbb{T}_i)_{i \ge 0}$ whose final tree is $\mathbb{T}$, and invoke the bijection to obtain a derivation. *Expansion schedule.* Start with $\mathbb{T}_0$ = one-node tree labelled $S$ (which equals the induced subtree of $\mathbb{T}$ on $\{\varepsilon\}$, since $\ell_\mathbb{T}(\varepsilon) = S$ by hypothesis). At stage $i$, if $\mathbb{T}_i = \mathbb{T}$, halt. Otherwise some node of $\mathbb{T}$ is missing from $\mathbb{T}_i$; since the absent set is prefix-closed in its complement (if $t \in \mathbb{T}_i$ has children $t0, \dots, tk$ in $\mathbb{T}$, then either all children are present or $t$ is a leaf of $\mathbb{T}_i$ with $\ell_i(t) \in V$), there exists a *shallowest* $\mathbb{T}_i$-leaf $t$ with $\ell_i(t) \in V$ and children in $\mathbb{T}$; choose the smallest-address such $t$ to break ties. Then $t$ is an internal node of $\mathbb{T}$, so $\mathbb{T}$ contains children $t0, \dots, tk$ with $\ell_\mathbb{T}(t) = A$ and the parse-tree condition supplies a production $A \to \ell_\mathbb{T}(t0) \cdots \ell_\mathbb{T}(tk) \in P$. Expand $t$ in $\mathbb{T}_i$ using this production to obtain $\mathbb{T}_{i+1}$; the children agree with those of $\mathbb{T}$ at $t$, so $\mathbb{T}_{i+1}$ embeds into $\mathbb{T}$. *Termination.* At each stage, $|T_{i+1}| > |T_i|$, and $T_i \subseteq T$ throughout. Since $|T| < \infty$ (the parse tree is finite by definition), the schedule halts after at most $|T|$ stages, and when it halts $\mathbb{T}_i = \mathbb{T}$. *Extraction of the derivation.* The resulting derivative sequence ends at $\mathbb{T}$, which is complete with yield $w$ and root label $S$. By the bijection from the previous step, this derivative sequence corresponds to a derivation $S = \alpha_0 \Rightarrow_G \cdots \Rightarrow_G \alpha_n = w$, witnessing $w \in \mathcal{L}(G)$. [/step] [step:Conclude the characterisation] Combining the forward and reverse directions: \begin{align*} w \in \mathcal{L}(G) \iff \exists\, \text{complete } G\text{-parse tree } \mathbb{T} \text{ with } \ell(\varepsilon) = S \text{ and } \sigma_\mathbb{T} = w. \end{align*} This is the stated characterisation, completing the proof. [/step]