[proofplan] The three implications are purely logical: each asserts that a rule satisfying the stronger defining condition automatically satisfies the weaker one. For each implication we extract the data of a $\mathcal{Q}$-rule (for $\mathcal{Q}$ the stronger class) and exhibit explicit witnesses — a variable $A$, strings $\gamma, \delta, \eta$, and a length comparison — that certify the weaker condition. Regular $\Rightarrow$ context-free requires only that a single-letter left side in $V$ with a right side of length at least one matches the context-free pattern. Context-free $\Rightarrow$ context-sensitive is witnessed by the empty context $\gamma = \delta = \varepsilon$. Context-sensitive $\Rightarrow$ noncontracting follows from the length identity $|\gamma \eta \delta| = |\gamma| + |\eta| + |\delta|$ together with the constraint $|\eta| \geq 1$. The chain of implications then follows by transitivity. [/proofplan] [step:Regular implies context-free] Let $(\alpha \to \beta)$ be a regular rule. By the definition of a regular rule there exists $A \in V$ with \begin{align*} \alpha &= A \end{align*} and either $\beta = a$ for some $a \in \Sigma$, or $\beta = aB$ for some $a \in \Sigma$ and $B \in V$. In either case, $\beta \in \Omega^\star$ is a non-empty string, so $|\beta| \geq 1$. The context-free defining condition is: $\alpha = A' \in V$ and $|\beta| > 0$. Taking $A' := A$, both parts are satisfied. Hence $(\alpha \to \beta)$ is context-free. [/step] [step:Context-free implies context-sensitive] Let $(\alpha \to \beta)$ be a context-free rule. By the definition of a context-free rule there exists $A \in V$ with \begin{align*} \alpha &= A, & |\beta| &\geq 1. \end{align*} The context-sensitive defining condition is: there exist $A' \in V$, $\gamma, \delta \in \Omega^\star$, and $\eta \in \Omega^+$ such that $\alpha = \gamma A' \delta$ and $\beta = \gamma \eta \delta$. We exhibit these witnesses by choosing the empty context on both sides: \begin{align*} A' &:= A \in V, & \gamma &:= \varepsilon \in \Omega^\star, & \delta &:= \varepsilon \in \Omega^\star, & \eta &:= \beta. \end{align*} Each choice lies in the required set: $A \in V$ by hypothesis, $\varepsilon \in \Omega^\star$ (the empty string is in the Kleene closure), and $\beta \in \Omega^+$ because $|\beta| \geq 1$ implies $\beta$ is a non-empty string. With these choices, \begin{align*} \gamma A' \delta &= \varepsilon \cdot A \cdot \varepsilon = A = \alpha, \\ \gamma \eta \delta &= \varepsilon \cdot \beta \cdot \varepsilon = \beta. \end{align*} So the required decomposition holds, and $(\alpha \to \beta)$ is context-sensitive. [/step] [step:Context-sensitive implies noncontracting] Let $(\alpha \to \beta)$ be a context-sensitive rule. By the definition of a context-sensitive rule there exist $A \in V$, $\gamma, \delta \in \Omega^\star$, and $\eta \in \Omega^+$ with \begin{align*} \alpha &= \gamma A \delta, & \beta &= \gamma \eta \delta. \end{align*} Length of a concatenation is additive on $\Omega^\star$ (each string's length is the number of its letters, and concatenation places letters end-to-end without overlap), so \begin{align*} |\alpha| &= |\gamma A \delta| = |\gamma| + |A| + |\delta| = |\gamma| + 1 + |\delta|, \\ |\beta| &= |\gamma \eta \delta| = |\gamma| + |\eta| + |\delta|. \end{align*} The constraint $\eta \in \Omega^+$ forces $|\eta| \geq 1$. Substituting, \begin{align*} |\beta| &= |\gamma| + |\eta| + |\delta| \geq |\gamma| + 1 + |\delta| = |\alpha|. \end{align*} Hence $|\alpha| \leq |\beta|$, i.e., $(\alpha \to \beta)$ is noncontracting. [guided] The defining condition for context-sensitive requires $\eta \in \Omega^+$ — a *non-empty* string — not $\eta \in \Omega^\star$. This is the hypothesis that powers the inequality. Without it, one could take $\eta = \varepsilon$ and the rule $\gamma A \delta \to \gamma \delta$ would erase a variable; such a rule would shorten the string ($|\alpha| = |\gamma| + 1 + |\delta|$ but $|\beta| = |\gamma| + |\delta|$), violating noncontraction. The computation itself is the length identity for concatenation, which holds for any strings in $\Omega^\star$ regardless of whether letters are variables or terminals. The inequality $|\eta| \geq 1$ immediately upgrades the equality $|\beta| = |\gamma| + |\eta| + |\delta|$ to the lower bound $|\beta| \geq |\gamma| + 1 + |\delta| = |\alpha|$. [/guided] [/step] [step:Chain the three implications] The three preceding steps establish: \begin{align*} \text{regular} &\implies \text{context-free}, \\ \text{context-free} &\implies \text{context-sensitive}, \\ \text{context-sensitive} &\implies \text{noncontracting}. \end{align*} Implication is transitive. Composing the three gives the full chain \begin{align*} \text{regular} &\implies \text{context-free} \implies \text{context-sensitive} \implies \text{noncontracting}, \end{align*} which is the second half of the statement of the theorem. Combined with the three individual implications proved above, this is the full conclusion. [/step]