Proving weak equivalence

The preceding formalisms describe derivations in rather different ways. A tree-adjoining grammar (TAG) combines elementary trees; a combinatory categorial grammar (CCG) combines categories; a multiple context-free grammar (MCFG) combines tuples of strings; and a minimalist grammar (MG) combines feature-bearing expressions. So what would it take to show that two of them generate the same string languages? Similar-looking examples are not enough.

We will again use double inclusion. After introducing it for set equality, we first applied it to the regular-expression evaluator. We then reused it for the lookaround language equation, DFA/NFA equivalence, the regular operations on FSAs, CFG closure, and the copy-language MCFG.

Why does the same argument establish weak equivalence? Let

\[ \mathcal{L}(F)=\{\mathbb{L}(H)\mid H\text{ is a grammar in }F\} \]

be the set of string languages generated by formalism $F$, and define $\mathcal{L}(G)$ in the same way. Weak equivalence means $\mathcal{L}(F)=\mathcal{L}(G)$. Since these are sets, double inclusion says that this equality holds if and only if $\mathcal{L}(F)\subseteq\mathcal{L}(G)$ and $\mathcal{L}(G)\subseteq\mathcal{L}(F)$.

We therefore need two claims:

for every grammar $H_F$ in $F$, construct a grammar $H_G$ in $G$ such that $\mathbb{L}(H_F)=\mathbb{L}(H_G)$; and
for every grammar $H_G$ in $G$, construct a grammar $H_F$ in $F$ such that $\mathbb{L}(H_G)=\mathbb{L}(H_F)$.

The first construction proves $\mathcal{L}(F)\subseteq\mathcal{L}(G)$: start with an arbitrary language in $\mathcal{L}(F)$, choose a grammar $H_F$ that generates it, and use the construction to obtain a grammar in $G$ for that same language. The second proves the reverse inclusion in exactly the same way. Double inclusion then gives $\mathcal{L}(F)=\mathcal{L}(G)$.

Each construction still needs its own correctness argument. We will state an invariant relating partial derivations in the two grammars, prove that the invariant holds at the base cases, and show that every derivation step preserves it. The invariant is what licenses the phrase “for that same language”; without it, constructing a grammar in the other formalism would not yet prove either inclusion.

Weak equivalence is the target

These proofs preserve terminal strings. They need not preserve derived trees, derivation order, elementary domains, lexical categories, or movement dependencies. A translation may introduce substantial administrative structure while preserving the string language.

Which arguments are complete here?

The arguments below differ in scope. The CFG–MCFG(1) and MCFG–LCFRS sections give complete proofs under the definitions in these notes. The later sections give construction guides because we have not introduced the normal forms needed to list every rule case; the cited theorems supply those cases.

A warm-up: CFG $=$ fan-out-one MCFG

We begin with an equivalence for which both translations can be written down completely:

\[ \text{CFG languages}=\text{MCFG}(1)\text{ languages}. \]

The notation $\text{MCFG}(1)$ means that every nonterminal has fan-out one. Thus, every nonterminal derives one string rather than a tuple with two or more components.

From a CFG to an MCFG

Let $G$ be an arbitrary CFG. Consider one of its rules, written so that terminals and nonterminals are separated:

\[ A\rightarrow u_0B_1u_1B_2\cdots B_ku_k, \]

where each $u_i$ is a possibly empty terminal string. Introduce one string variable $x_i$ for the yield of each $B_i$, and replace the CFG rule with

\[ A(u_0x_1u_1x_2\cdots x_ku_k) \leftarrow B_1(x_1),\ldots,B_k(x_k). \]

A lexical rule such as $A\rightarrow a$ becomes $A(a)\leftarrow\epsilon$, and an epsilon rule becomes $A(\epsilon)\leftarrow\epsilon$. Apply this replacement to every rule of $G$.

We now prove that the translation preserves yields. The invariant is:

If a CFG nonterminal $A$ derives $w$, then the translated MCFG derives $A(w)$, and conversely.

For the base case, a one-step CFG derivation $A\Rightarrow u$ using a terminal-only rule has the translated MCFG rule $A(u)\leftarrow\epsilon$. Thus, both grammars derive the same $u$ from $A$.

For the inductive step, suppose the CFG uses the displayed rule and each child derives $B_i\Rightarrow^*w_i$. By the induction hypothesis, the MCFG derives $B_i(w_i)$ for every child. Substituting those values for the variables in the translated rule derives

\[ A(u_0w_1u_1w_2\cdots w_ku_k). \]

That string is exactly the yield of the CFG derivation. Reading the same reasoning upward proves the converse: every use of the MCFG rule corresponds to the original CFG rule, and every antecedent tuple has only one component. Taking $A=S$ establishes equality of the two string languages.

Here is a small trace. Take the CFG rules $S\rightarrow aSb$ and $S\rightarrow\epsilon$. Their translations are

\[ S(axb)\leftarrow S(x) \qquad\text{and}\qquad S(\epsilon)\leftarrow\epsilon. \]

The CFG derivation $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ corresponds to the bottom-up MCFG value trace $S(\epsilon)$, $S(ab)$, $S(aabb)$. At each step, the MCFG variable $x$ is replaced by the one string derived by the recursive child. Reading the trace backward recovers the same CFG rule applications, so this example exhibits both directions of the invariant.

From a fan-out-one MCFG to a CFG

Now let $G'$ be an arbitrary linear, nonerasing fan-out-one MCFG. A rule of $G'$ has one output component. For instance,

\[ A(u_0x_2u_1x_1u_2) \leftarrow B_1(x_1),B_2(x_2) \]

places the yield of $B_2$ before the yield of $B_1$. Replace each variable in the output by the nonterminal that supplies it. The resulting CFG rule is

\[ A\rightarrow u_0B_2u_1B_1u_2. \]

Linearity guarantees that no variable must be copied. Nonerasure guarantees that no child yield disappears. And fan-out one guarantees that a child contributes one contiguous string, which a CFG nonterminal can represent.

The invariant and induction are now the same as in the first direction. A partial MCFG derivation of $A(w)$ corresponds to a CFG derivation $A\Rightarrow^*w$, and every rule application preserves that correspondence. We have proved both containments, so the equality follows.

For a concrete instance of the displayed rule, let $u_0=a$, $u_1=b$, and $u_2=c$, and suppose $B_1$ derives $p$ while $B_2$ derives $q$. The MCFG produces $A(aqbpc)$. The translated CFG rule is $A\rightarrow aB_2bB_1c$, which derives the same string $aqbpc$. The order of the two child yields may change, but each child still contributes one contiguous substring.

Question

Why does this argument stop working when a nonterminal has fan-out two?

Answer

A fan-out-two child supplies two strings whose final positions need not be adjacent. Replacing that child with one CFG nonterminal would force the two components to form one contiguous substring. The one-component invariant used in the proof would thus fail.

MCFG $=$ LCFRS

Under the definitions used in these notes, an MCFG rule and an LCFRS production package the same information in different notation. Both associate a nonterminal with a fixed number of string components, and both combine child components with a linear, nonerasing tuple function. The standard definitions sometimes permit erasing MCFG rules; those rules can be removed without changing weak generative capacity (Seki et al. 1991; Michaelis 2001b). We work directly with the nonerasing version.

Consider the MCFG rule

\[ A(x_1y_1,\;y_2x_2) \leftarrow B(x_1,x_2),C(y_1,y_2). \]

Define the tuple function

\[ f((x_1,x_2),(y_1,y_2))=(x_1y_1,\;y_2x_2). \]

The corresponding LCFRS production is

\[ A\rightarrow f(B,C). \]

This gives the first translation: replace each MCFG rule by an LCFRS production whose function is the tuple pattern written on the left side of the MCFG rule. For the reverse translation, expand each LCFRS function into that tuple pattern.

The correctness invariant is exact equality of tuples:

A nonterminal $A$ derives tuple $\mathbf{w}$ in the MCFG if and only if it derives the same tuple $\mathbf{w}$ in the LCFRS.

A rule without nonterminal antecedents gives the same constant tuple in both systems, so the base case holds. For the inductive step, assume that corresponding child derivations produce the same tuples. The two translated rules apply the same function $f$ to those tuples. They must thus produce the same parent tuple. Induction on derivation height proves the invariant for every nonterminal, including the fan-out-one start symbol.

For instance, suppose $B$ derives $(p,q)$ and $C$ derives $(r,s)$. The MCFG rule above returns $A(pr,sq)$. The LCFRS production applies $f((p,q),(r,s))$ and returns the same tuple $(pr,sq)$. Nothing else changes in this translation: the nonterminal names, child tuples, and tuple function are the same objects in different notation.

This equivalence is unusually direct. The translations below require more work because their two formalisms store partial derivations in different kinds of objects.

TAG and constrained fan-out-two LCFRS

The central operation in TAG is adjunction. An auxiliary tree with root and foot $X$ contributes a context around the tree inserted at its foot. If the terminals to the left of the foot spell $u$ and those to the right spell $v$, represent that auxiliary tree by the pair

\[ (u,v). \]

If the tree at the adjunction site has yield $w$, the adjoined tree has yield

\[ uwv. \]

This is the one-gap invariant: a partially derived auxiliary tree is represented by the material on the two sides of its single foot. Fan-out two is sufficient because there is one distinguished gap and hence two surrounding string components.

From TAG to constrained LCFRS

Fix an arbitrary TAG. We construct LCFRS nonterminals for the nodes of its finite elementary trees. A nonterminal associated with an initial-tree fragment has fan-out one because that fragment has no foot. A nonterminal associated with an auxiliary-tree fragment containing the foot has fan-out two because its yield has a left component and a right component.

There are three construction cases.

Local tree structure. Reading the frontier of an elementary-tree fragment from left to right gives a linear tuple function. Terminals are written directly into the output, and substitution nodes contribute variables supplied by fan-out-one children.
Substitution. If an initial tree with yield $w$ substitutes at an $X\!\downarrow$ node, the variable for that node is replaced by $w$. This is ordinary one-component concatenation.
Adjunction. If an auxiliary derivation contributes $(u,v)$ and the derivation at the adjunction site contributes $w$, the translated rule returns $uwv$. If one auxiliary context $(u_1,v_1)$ adjoins inside another $(u_2,v_2)$, their combined context is $(u_2u_1,v_1v_2)$; placing $w$ in its gap yields $u_2u_1wv_1v_2$.

We prove correctness by induction on the number of substitutions and adjunctions. Before either operation applies, every initial tree has the same one-component frontier yield in both grammars, and every auxiliary tree has the same pair of strings around its foot. This establishes the base cases.

For the inductive step, suppose the invariant holds for the derived trees being combined. In a substitution step, both derivations replace the same frontier position by the same child yield. In an adjunction step, both derivations place the same site yield between the same left and right components. Thus, the resulting initial tree again has the same yield, or the resulting auxiliary tree again has the same context pair. At the start symbol there is no foot, so the LCFRS and TAG derive exactly the same terminal strings.

Take an auxiliary tree whose frontier is schematically $\text{will}\;X^*\;\text{today}$. The translation records the pair $(\text{will},\text{today})$. If the $X$ subtree has yield chase rabbits, TAG adjunction produces will chase rabbits today. The LCFRS rule inserts the same site yield between the two components and produces that same string. Conversely, any use of this particular one-gap rule identifies the two surrounding components and the inserted $X$ yield, so it reconstructs the corresponding adjunction step.

Why the converse needs a restriction

An arbitrary fan-out-two LCFRS can combine pairs in ways that do not describe one context around one gap. It might cross or independently interleave the components of several children. A single TAG auxiliary tree cannot in general represent those arrangements. Thus, the preceding construction proves

\[ \text{TAG languages}\subseteq\text{fan-out-two LCFRS languages}, \]

not equality with all fan-out-two LCFRSs.

For the converse used in this characterization, restrict the LCFRS to the root–foot normal form produced by the construction above. In this normal form, a fan-out-two nonterminal always denotes one context around one gap, and every rule describes local tree structure, substitution, or insertion into that gap. This name is local to these notes; it identifies the image of the TAG compilation rather than every formalism called a well-nested fan-out-two LCFRS.

We can now reverse the three cases. A fan-out-one rule becomes an initial-tree fragment; a paired nonterminal becomes an auxiliary-tree fragment whose root and foot share a label; and a function that inserts one yield between the two components of a context becomes adjunction. The rule restriction guarantees that these fragments can be arranged around one foot without crossing components.

The reverse invariant is again the one-gap invariant. A derived pair $(u,v)$ corresponds to an auxiliary derived tree whose frontier is $uX^*v$, and a derived singleton $(w)$ corresponds to an initial derived tree with yield $w$. The base rules create the corresponding elementary fragments. Each one-gap tuple combination becomes either substitution or adjunction and preserves the invariant. This proves equality between TAG and the appropriately constrained fan-out-two system, while leaving the proper inclusion into unrestricted MCFG intact.

The TAG $=$ HG $=$ LIG $=$ restricted-CCG construction guide

The four-formalism theorem also includes head grammar (HG) (Vijay-Shanker and Weir 1994). We will first connect HG to the one-gap representation used for TAG and then use linear indexed grammar (LIG) to connect TAG with restricted CCG.

TAG and HG

A head grammar derives headed strings. Write one as

\[\alpha\widehat{x}\beta,\]

where the marked terminal $x$ is the distinguished head. The visible yield is $\alpha x\beta$. For the translation, encode this headed string as the pair

\[ (\alpha x,\beta). \]

The pair places a cut immediately after the head. This is an administrative cut, not a claim about the linguistic head of a TAG tree.

Head grammars use concatenation and wrapping operations. Concatenation joins the visible yields of several headed strings and selects one of their heads as the head of the result. Wrapping is easier to see with two strings:

\[ w(\alpha\widehat{x}\beta,\gamma\widehat{y}\delta) =\alpha x\gamma\widehat{y}\delta\beta. \]

Under the pair encoding, the two inputs are $(\alpha x,\beta)$ and $(\gamma y,\delta)$, and the output is

\[ (\alpha x\gamma y,\delta\beta). \]

Thus, wrapping combines two pairs by concatenating their left components in forward order and their right components in reverse order. This is exactly the context-composition pattern used when one TAG auxiliary context is inserted into another. The head-grammar concatenation operations are also linear tuple functions: they concatenate every input yield once and place the output cut at the head selected by the operation.

Translate each HG rule into the corresponding tuple rule. The invariant is:

HG nonterminal $A$ derives $\alpha\widehat{x}\beta$ if and only if its tuple translation derives $A(\alpha x,\beta)$.

A terminal-only headed rule gives the same pair and establishes the base case. For the inductive step, assume the children satisfy the invariant. A concatenation rule applies the same left-to-right concatenation and retains the same selected cut in both representations. A wrapping rule applies the pair function just calculated. Thus, each HG derivation has a tuple derivation with the same visible yield.

What about the reverse direction? We cannot simply turn every pair $(p,q)$ into a headed string. The encoding $(\alpha x,\beta)$ requires the left component to end in the distinguished head $x$; inventing an “empty head” would change the formalism and, unless it were removed by an additional construction, the string language. The full proof first normalizes the tuple rules so that every distinguished cut is anchored in this way. It then replaces the anchored cut with the corresponding head and checks the finite concatenation and wrapping cases one by one (Vijay-Shanker and Weir 1994).

This anchoring condition is the missing reverse invariant:

A tuple configuration corresponds to an HG object only if its distinguished cut is licensed by the head annotation carried by that configuration.

With that condition in place, a context-composition rule becomes wrapping, and an ordinary frontier combination becomes a head-grammar concatenation operation. The TAG and HG constructions can then be related through the same normalized one-gap representation. The pair calculation gives the wrapping case, while the anchoring and normal-form cases are needed for the full theorem.

A small wrapping trace makes the anchored cut visible. Encode $\text{the}\;\widehat{\text{dog}}\;\text{today}$ as $(\text{the dog},\text{today})$ and $\text{will}\;\widehat{\text{run}}\;\text{now}$ as $(\text{will run},\text{now})$. Wrapping the second headed string inside the first gives $\text{the dog will}\;\widehat{\text{run}}\;\text{now today}$, whose pair is $(\text{the dog will run},\text{now today})$. The pair calculation preserves both the visible yield and the cut after run. The reverse construction works for this trace because that cut is anchored by the marked head; the general reverse direction requires the normalization just described.

TAG and LIG

A LIG attaches a stack of indices to a nonterminal, but only one child in a production inherits the active stack. We will call that child the spine child.

Begin with the TAG-to-LIG direction. Every auxiliary tree has a unique path from its root to its foot. Treat this path as a spine. Entering an auxiliary tree pushes a symbol that identifies the pending material around the foot; following the root-to-foot path passes the stack to the next spine node; and completing the auxiliary tree pops that symbol after its off-spine subtrees have been derived. Substitution sites become ordinary context-free children because they do not carry the active stack.

The invariant is:

A TAG derivation with a sequence of unfinished auxiliary trees along its active root-to-foot path corresponds to a LIG nonterminal whose index stack lists exactly those auxiliary trees in nesting order.

With no unfinished adjunction, the stack is empty and an initial tree is simulated by ordinary productions. This is the base case. Adjoining one auxiliary tree adds one unfinished root-to-foot dependency, and the LIG pushes its index. Descending the spine leaves that index available while off-spine material is completed. Reaching the foot discharges the dependency, so the LIG pops the same index. Substitution does not affect the spine and thus leaves the stack unchanged. Induction on the TAG derivation proves that every TAG yield is a LIG yield.

For the reverse direction, first normalize the LIG so that a production changes the stack by at most one symbol and still passes it to at most one child. Because only one child inherits the active stack, the stack-carrying nodes form a single spine through each relevant part of the derivation tree. For each compatible push and pop rule schema, create an auxiliary-tree template: the push site becomes its root, the pop site becomes its foot, and ordinary children become off-spine substitution sites. The possibly unbounded material between the two sites is produced recursively by further substitutions and adjunctions; it is not copied into one elementary tree. Stack-free productions become initial-tree fragments. The grammar has finitely many rules and stack symbols, so only finitely many templates are required.

Now use the reverse invariant: the LIG stack records the auxiliary trees whose roots have been entered but whose feet have not yet been reached. A push starts adjunction, transmission follows the auxiliary spine, and the matching pop reaches the foot. Reading either derivation from left to right thus gives the same terminal yield. This establishes both containments between TAG and LIG.

For a minimal trace, let $\beta$ be an auxiliary tree with schematic frontier $\text{will}\;X^*\;\text{today}$, and let the initial $X$ tree yield run. Entering $\beta$ changes the LIG stack from $[]$ to $[\beta]$. The stack is passed down the unique spine while will is produced off its left side. Reaching the foot matches the initial $X$ tree, produces run, and pops $\beta$; the remaining off-spine material produces today. Both derivations yield will run today. In the reverse direction, the matching push and pop delimit exactly the auxiliary-tree template for this example.

LIG and restricted CCG

A complex CCG category can be viewed as an atomic result together with a stack of unsatisfied arguments. For instance,

$$ ((SNP)/NP)/PP

has atomic result $S$ and three pending arguments, with slash directions recording the sides on which they must be discharged. Under the restrictions in the equivalence theorem, application and bounded-degree composition inspect and modify only a bounded portion of this argument stack.

Translate a restricted CCG category into a LIG nonterminal whose finite control records the bounded part of the category currently inspected by a combinator, and whose index stack records the unbounded remainder of its argument structure. A lexical category initializes that representation. Application removes the matching exposed argument. Composition transfers a bounded sequence of arguments from one category to another, which is simulated by a fixed sequence of LIG stack operations.

Why is the translated grammar finite? There are finitely many lexical categories and combinator schemata, and the composition degree has a fixed bound. The finite control thus has only finitely many local cases to distinguish. The stack may be unbounded during a derivation, but its alphabet is drawn from the finite collection of argument records induced by those cases. An indexed grammar thus combines finitely many productions with an unbounded stack.

The category-stack invariant states:

A CCG constituent with category $C$ and yield $w$ corresponds to a LIG constituent with yield $w$ whose finite control and stack encode exactly $C$.

Lexical entries establish the invariant. Each licensed combinator has a corresponding LIG rule sequence that performs the same bounded category operation and concatenates the same left and right yields. Thus, induction on CCG derivations gives the CCG-to-LIG containment.

For the reverse direction, first place the LIG in the restricted normal form used by the theorem. We then encode a stack symbol as one argument layer of a CCG category. A normalized push adds that layer; a normalized pop discharges it; and a rule that transmits the stack to the unique spine child becomes a bounded composition schema. Stack-free terminal and branching rules become lexical and application cases. Because the normalized LIG has finitely many rule and stack-symbol types, this construction produces a finite CCG grammar. Reading the category-stack invariant from LIG configurations to CCG categories gives the reverse simulation. The full proof checks each normalized LIG rule against its CCG schema; without that case list, “put the stack in the category” would only name the idea, not prove the containment.

For instance, the familiar transitive-verb derivation illustrates the stack invariant. Treat $(S\backslash NP)/NP$ as result $S$ with a leftward $NP$ argument and a currently exposed rightward $NP$ argument. Combining it with the right-hand $NP$ in chase rabbits removes that exposed argument and leaves $S\backslash NP$. Combining the result with the left-hand $NP$ in greyhounds chase rabbits removes the remaining argument and leaves $S$. The corresponding normalized LIG operations pop the same two argument records in the same order while producing the same three-word yield. This trace illustrates application; bounded composition requires the additional finite rule cases supplied by the theorem.

The rule-by-rule constructions in the cited theorem give

\[ \text{TAG}=\text{HG}=\text{LIG}=\text{restricted CCG} \]

at the level of string languages. The restriction on CCG is part of the theorem. Adding arbitrary combinators would invalidate the finite list of LIG simulations used in the proof.

The MG $=$ MCFG/LCFRS construction guide

The MG equivalence again requires two constructions (Michaelis 2001a, 2001b; Harkema 2001). The main problem is movement: an MG expression may contain pronounced material that will occupy several separated positions in the final string. An MCFG tuple provides a direct representation of those pieces.

From MG to MCFG

Fix an MG of the kind treated by Michaelis (2001a): its feature sets and lexicon are finite, features are checked from the left edge of their sequences, and the relevance condition permits at most one active maximal projection for each licensee feature.

For every partial MG expression, record two kinds of information:

its remaining head-feature sequence and the feature types of its active movers; and
an $m+2$-tuple $(\pi_H,\pi_0,\ldots,\pi_m)$, separating the phonetic head material, the residual yield of the whole expression, and the residual pronounced material associated with each of the $m$ licensee types.

The first record is a configuration type. There are only finitely many configuration types because the lexicon and feature inventory are finite and the movement condition bounds the mover store. Create one MCFG nonterminal for each type. Its fan-out is the number of strings in the corresponding tuple.

The invariant is:

An MG expression of type $\tau$ with ordered yield pieces $\mathbf{w}$ exists if and only if the MCFG nonterminal $A_\tau$ derives the tuple $\mathbf{w}$.

Lexical items establish the base case. A pronounced lexical item contributes its phonological string to the appropriate component; a silent item contributes $\epsilon$. Its unconsumed features determine $\tau$.

There are then two inductive cases.

Merge. Suppose one expression begins with selector $=x$ and another supplies category $x$. Merge consumes the matching features and concatenates their head yields in the order fixed by the MG definition. Their mover stores are carried into the result. The corresponding MCFG rule takes the two child tuples, concatenates exactly the components joined by Merge, and passes every other component through once.
Move. Suppose an expression begins with licensor $+f$ and contains the uniquely matching mover with $-f$. Move consumes both features and places the mover yield in its pronounced position. The corresponding MCFG rule removes that yield from its mover component and concatenates it into the designated output component. Every string variable again occurs exactly once.

In each case, the output configuration type is determined by the remaining features, and the tuple function reproduces the MG word order. Thus, the invariant is preserved. A complete MG expression has no unchecked features or active movers and has one terminal yield. The corresponding fan-out-one start nonterminal derives exactly that yield, proving the MG-to-MCFG containment.

Consider a partial MG expression whose residual yield is likes rabbits and whose active $wh$ mover has yield who. Suppose the phonetic-head component and the slots for every other licensee type are empty. If we suppress those empty components, the relevant part of the tuple is $(\text{likes rabbits},\text{who})$. When a $+wh$ licensor matches the mover’s $-wh$ feature, Move consumes the two features and places the mover before the residual yield, producing who likes rabbits. On the displayed components, the matching MCFG step applies $f(x,y)=yx$. Reading this step in reverse recovers which mover component was discharged, provided that the configuration type records the matching feature.

From LCFRS to MG

For the other direction, first replace the MCFG with a weakly equivalent LCFRS of rank at most two. Corollary 2.8 of Michaelis (2001b, 231) guarantees this replacement; rank at most two means that each production has at most two nonterminal children. We can thus handle a finite set of local cases without changing the string language.

Consider a binary production such as

\[ A(x_1y_1,\;y_2x_2) \rightarrow B(x_1,x_2),C(y_1,y_2). \]

The MG translation gives the components supplied by $B$ and $C$ distinct movement features. It then performs three jobs:

lexical feature sequences identify the production and select encodings of its $B$ and $C$ children;
Merge places those encodings in one expression while their tuple components remain identifiable as movers; and
a fixed sequence of licensors exposes the pieces in the ledger order $x_1,y_1\mid y_2,x_2$, where the bar marks the boundary between the two output components specified by the LCFRS function.

The vertical boundary between $x_1y_1$ and $y_2x_2$ is part of the package’s bookkeeping. The sentence above does not mean that an intermediate MG expression has already pronounced the two fields as one contiguous string. Rather, the feature gadget keeps the fields distinguishable until a higher production consumes the package. The exact feature names are administrative. What matters is that the production is finite and linear: it mentions finitely many variables, and each variable occurs once. The MG can thus assign one licensee to each component and use a finite feature sequence to place each component exactly once. A constant terminal in the LCFRS function is supplied by a pronounced lexical item in the corresponding package.

There are only finitely many such gadgets. The LCFRS has finitely many productions, and each production mentions finitely many component variables. We create a fixed lexical package for each production rather than a new lexical item for each derived tuple of strings. The strings themselves enter through the recursively selected child packages.

The reverse invariant is:

An LCFRS derivation of $A(\mathbf{w})$ exists if and only if a complete MG production package of category $A$ has still-separated pronounced pieces, in the order named by the package, equal to $\mathbf{w}$.

For the displayed LCFRS rule, suppose $B$ derives $(a,d)$ and $C$ derives $(b,c)$. Substitution gives

\[ A(x_1y_1,y_2x_2)=A(ab,cd). \]

The MG production package selects the encodings of those two child tuples, keeps the four pieces identifiable, and discharges their licensees in the ledger order $a,b\mid c,d$. The resulting package thus records $(ab,cd)$ as well. Conversely, the lexical item that identifies this package determines the displayed LCFRS production, and the four discharged pieces determine its two child tuples.

Constant productions establish the invariant with lexical packages. For the inductive step, assume that the packages for the child nonterminals encode the tuples derived by those children. The selector features for the parent production Merge those packages. Its licensors then Move the component yields into the order written by the LCFRS tuple function. Since the function is linear and nonerasing, no component is copied or lost. The resulting parent package thus encodes exactly the tuple derived by the LCFRS rule.

This establishes the forward half of the invariant. For the reverse half, take a completed MG production package and inspect the lexical item that identifies its parent-production gadget. Its selector sequence requires packages of exactly the nonterminal types on the right side of that LCFRS production. Its movement features can discharge each component exactly once and only in the order specified by the tuple function. Decoding the child packages recursively thus reconstructs an LCFRS derivation with the same tuple. Induction on package height establishes both directions at the start symbol. The start symbol has fan-out one, so the completed MG package and the LCFRS derivation have the same terminal yield.

Keeping the conclusions and proof status separate

The arguments support three different conclusions, with different proof status in these notes:

We proved directly that fan-out-one MCFGs and CFGs generate the same string languages.
We proved directly that the MCFG and LCFRS notations used here describe the same linear, nonerasing tuple operations.
We traced the invariants behind the TAG–HG–LIG–restricted-CCG and MG–MCFG equivalence theorems. The cited sources prove the full results by checking the normal-form production cases that the construction guides summarize.

These results do not collapse the entire unit into one class. In particular,

\[ \text{CFG} \subsetneq \text{TAG} \subsetneq \text{MCFG}. \]

Nor do they say that corresponding derivations express the same linguistic analysis. The translations establish weak equivalence by preserving yields. Questions about elementary domains, derivation trees, lexicalization, and the interpretation of movement remain separate.

Question

Suppose we have translated every TAG into a fan-out-two LCFRS with the same language. Have we proved that TAG and fan-out-two LCFRS are weakly equivalent?

Answer

No. We have proved only the TAG-to-LCFRS containment. Equality would require a reverse translation for every fan-out-two LCFRS, and that claim is false without restricting the LCFRS rules. Unrestricted fan-out-two systems can generate string languages outside the TAG class.

References

Harkema, Hendrik. 2001. “Parsing Minimalist Languages.” PhD thesis, University of California, Los Angeles. https://linguistics.ucla.edu/people/stabler/paris12/Harkema01.pdf.

Michaelis, Jens. 2001a. “Derivational Minimalism Is Mildly Context-Sensitive.” Logical Aspects of Computational Linguistics: Third International Conference, LACL ’98, Selected Papers, Lecture notes in computer science, vol. 2014: 179–98. https://doi.org/10.1007/3-540-45738-0_11.

Michaelis, Jens. 2001b. “Transforming Linear Context-Free Rewriting Systems into Minimalist Grammars.” Logical Aspects of Computational Linguistics, LNCS, vol. 2099: 228–44. https://doi.org/10.1007/3-540-48199-0_14.

Seki, Hiroyuki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. 1991. “On Multiple Context-Free Grammars.” Theoretical Computer Science 88 (2): 191–229. https://doi.org/10.1016/0304-3975(91)90374-B.

Vijay-Shanker, K., and David J. Weir. 1994. “The Equivalence of Four Extensions of Context-Free Grammars.” Mathematical Systems Theory 27 (6): 511–46. https://doi.org/10.1007/BF01191624.

--- title: Proving weak equivalence bibliography: ../../references.bib --- The preceding formalisms describe derivations in rather different ways. A tree-adjoining grammar (TAG) combines elementary trees; a combinatory categorial grammar (CCG) combines categories; a multiple context-free grammar (MCFG) combines tuples of strings; and a minimalist grammar (MG) combines feature-bearing expressions. So what would it take to show that two of them generate the same string languages? Similar-looking examples are not enough. We will again use [**double inclusion**](../../languages-as-formal-objects/set-relations.qmd#equality-by-double-inclusion). After introducing it for set equality, we first applied it to the [regular-expression evaluator](../../grammars-as-languages/evaluating-regular-expressions.qmd). We then reused it for the [lookaround language equation](../../grammars-as-languages/lookarounds.qmd#formal-perspective), [DFA/NFA equivalence](../../phonological-patterns/formal-definition/two-equivalent-definitions.qmd#dfas-are-equivalent-to-nfas), the [regular operations on FSAs](../../phonological-patterns/formal-definition/the-regular-operations.qmd), [CFG closure](../../morphological-patterns/operations.qmd#why-the-constructions-work), and the [copy-language MCFG](mcfgs-and-lcfrs.qmd#a-copying-language). Why does the same argument establish weak equivalence? Let $$ \mathcal{L}(F)=\{\mathbb{L}(H)\mid H\text{ is a grammar in }F\} $$ be the set of string languages generated by formalism $F$, and define $\mathcal{L}(G)$ in the same way. [Weak equivalence](../../phonological-patterns/generation.qmd) means $\mathcal{L}(F)=\mathcal{L}(G)$. Since these are sets, double inclusion says that this equality holds if and only if $\mathcal{L}(F)\subseteq\mathcal{L}(G)$ and $\mathcal{L}(G)\subseteq\mathcal{L}(F)$. We therefore need two claims: 1. for every grammar $H_F$ in $F$, construct a grammar $H_G$ in $G$ such that $\mathbb{L}(H_F)=\mathbb{L}(H_G)$; and 2. for every grammar $H_G$ in $G$, construct a grammar $H_F$ in $F$ such that $\mathbb{L}(H_G)=\mathbb{L}(H_F)$. The first construction proves $\mathcal{L}(F)\subseteq\mathcal{L}(G)$: start with an arbitrary language in $\mathcal{L}(F)$, choose a grammar $H_F$ that generates it, and use the construction to obtain a grammar in $G$ for that same language. The second proves the reverse inclusion in exactly the same way. Double inclusion then gives $\mathcal{L}(F)=\mathcal{L}(G)$. Each construction still needs its own correctness argument. We will state an invariant relating partial derivations in the two grammars, prove that the invariant holds at the base cases, and show that every derivation step preserves it. The invariant is what licenses the phrase “for that same language”; without it, constructing a grammar in the other formalism would not yet prove either inclusion. ::: {.callout-caution} ## Weak equivalence is the target These proofs preserve terminal strings. They need not preserve derived trees, derivation order, elementary domains, lexical categories, or movement dependencies. A translation may introduce substantial administrative structure while preserving the string language. ::: ::: {.callout-note} ## Which arguments are complete here? The arguments below differ in scope. The CFG–MCFG(1) and MCFG–LCFRS sections give complete proofs under the definitions in these notes. The later sections give construction guides because we have not introduced the normal forms needed to list every rule case; the cited theorems supply those cases. ::: ## A warm-up: CFG $=$ fan-out-one MCFG We begin with an equivalence for which both translations can be written down completely: $$ \text{CFG languages}=\text{MCFG}(1)\text{ languages}. $$ The notation $\text{MCFG}(1)$ means that every nonterminal has fan-out one. Thus, every nonterminal derives one string rather than a tuple with two or more components. ### From a CFG to an MCFG Let $G$ be an arbitrary CFG. Consider one of its rules, written so that terminals and nonterminals are separated: $$ A\rightarrow u_0B_1u_1B_2\cdots B_ku_k, $$ where each $u_i$ is a possibly empty terminal string. Introduce one string variable $x_i$ for the yield of each $B_i$, and replace the CFG rule with $$ A(u_0x_1u_1x_2\cdots x_ku_k) \leftarrow B_1(x_1),\ldots,B_k(x_k). $$ A lexical rule such as $A\rightarrow a$ becomes $A(a)\leftarrow\epsilon$, and an epsilon rule becomes $A(\epsilon)\leftarrow\epsilon$. Apply this replacement to every rule of $G$. We now prove that the translation preserves yields. The invariant is: > If a CFG nonterminal $A$ derives $w$, then the translated MCFG derives $A(w)$, and conversely. For the base case, a one-step CFG derivation $A\Rightarrow u$ using a terminal-only rule has the translated MCFG rule $A(u)\leftarrow\epsilon$. Thus, both grammars derive the same $u$ from $A$. For the inductive step, suppose the CFG uses the displayed rule and each child derives $B_i\Rightarrow^*w_i$. By the induction hypothesis, the MCFG derives $B_i(w_i)$ for every child. Substituting those values for the variables in the translated rule derives $$ A(u_0w_1u_1w_2\cdots w_ku_k). $$ That string is exactly the yield of the CFG derivation. Reading the same reasoning upward proves the converse: every use of the MCFG rule corresponds to the original CFG rule, and every antecedent tuple has only one component. Taking $A=S$ establishes equality of the two string languages. Here is a small trace. Take the CFG rules $S\rightarrow aSb$ and $S\rightarrow\epsilon$. Their translations are $$ S(axb)\leftarrow S(x) \qquad\text{and}\qquad S(\epsilon)\leftarrow\epsilon. $$ The CFG derivation $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ corresponds to the bottom-up MCFG value trace $S(\epsilon)$, $S(ab)$, $S(aabb)$. At each step, the MCFG variable $x$ is replaced by the one string derived by the recursive child. Reading the trace backward recovers the same CFG rule applications, so this example exhibits both directions of the invariant. ### From a fan-out-one MCFG to a CFG Now let $G'$ be an arbitrary linear, nonerasing fan-out-one MCFG. A rule of $G'$ has one output component. For instance, $$ A(u_0x_2u_1x_1u_2) \leftarrow B_1(x_1),B_2(x_2) $$ places the yield of $B_2$ before the yield of $B_1$. Replace each variable in the output by the nonterminal that supplies it. The resulting CFG rule is $$ A\rightarrow u_0B_2u_1B_1u_2. $$ Linearity guarantees that no variable must be copied. Nonerasure guarantees that no child yield disappears. And fan-out one guarantees that a child contributes one contiguous string, which a CFG nonterminal can represent. The invariant and induction are now the same as in the first direction. A partial MCFG derivation of $A(w)$ corresponds to a CFG derivation $A\Rightarrow^*w$, and every rule application preserves that correspondence. We have proved both containments, so the equality follows. For a concrete instance of the displayed rule, let $u_0=a$, $u_1=b$, and $u_2=c$, and suppose $B_1$ derives $p$ while $B_2$ derives $q$. The MCFG produces $A(aqbpc)$. The translated CFG rule is $A\rightarrow aB_2bB_1c$, which derives the same string $aqbpc$. The order of the two child yields may change, but each child still contributes one contiguous substring. ::: {.callout-note collapse="true"} ## Question Why does this argument stop working when a nonterminal has fan-out two? ::: {.callout-tip collapse="true"} ## Answer A fan-out-two child supplies two strings whose final positions need not be adjacent. Replacing that child with one CFG nonterminal would force the two components to form one contiguous substring. The one-component invariant used in the proof would thus fail. ::: ::: ## MCFG $=$ LCFRS Under the definitions used in these notes, an MCFG rule and an LCFRS production package the same information in different notation. Both associate a nonterminal with a fixed number of string components, and both combine child components with a linear, nonerasing tuple function. The standard definitions sometimes permit erasing MCFG rules; those rules can be removed without changing weak generative capacity [@seki1991multiple; @michaelis2001transforming]. We work directly with the nonerasing version. Consider the MCFG rule $$ A(x_1y_1,\;y_2x_2) \leftarrow B(x_1,x_2),C(y_1,y_2). $$ Define the tuple function $$ f((x_1,x_2),(y_1,y_2))=(x_1y_1,\;y_2x_2). $$ The corresponding LCFRS production is $$ A\rightarrow f(B,C). $$ This gives the first translation: replace each MCFG rule by an LCFRS production whose function is the tuple pattern written on the left side of the MCFG rule. For the reverse translation, expand each LCFRS function into that tuple pattern. The correctness invariant is exact equality of tuples: > A nonterminal $A$ derives tuple $\mathbf{w}$ in the MCFG if and only if it derives the same tuple $\mathbf{w}$ in the LCFRS. A rule without nonterminal antecedents gives the same constant tuple in both systems, so the base case holds. For the inductive step, assume that corresponding child derivations produce the same tuples. The two translated rules apply the same function $f$ to those tuples. They must thus produce the same parent tuple. Induction on derivation height proves the invariant for every nonterminal, including the fan-out-one start symbol. For instance, suppose $B$ derives $(p,q)$ and $C$ derives $(r,s)$. The MCFG rule above returns $A(pr,sq)$. The LCFRS production applies $f((p,q),(r,s))$ and returns the same tuple $(pr,sq)$. Nothing else changes in this translation: the nonterminal names, child tuples, and tuple function are the same objects in different notation. This equivalence is unusually direct. The translations below require more work because their two formalisms store partial derivations in different kinds of objects. ## TAG and constrained fan-out-two LCFRS The central operation in TAG is adjunction. An auxiliary tree with root and foot $X$ contributes a context around the tree inserted at its foot. If the terminals to the left of the foot spell $u$ and those to the right spell $v$, represent that auxiliary tree by the pair $$ (u,v). $$ If the tree at the adjunction site has yield $w$, the adjoined tree has yield $$ uwv. $$ This is the **one-gap invariant**: a partially derived auxiliary tree is represented by the material on the two sides of its single foot. Fan-out two is sufficient because there is one distinguished gap and hence two surrounding string components. ### From TAG to constrained LCFRS Fix an arbitrary TAG. We construct LCFRS nonterminals for the nodes of its finite elementary trees. A nonterminal associated with an initial-tree fragment has fan-out one because that fragment has no foot. A nonterminal associated with an auxiliary-tree fragment containing the foot has fan-out two because its yield has a left component and a right component. There are three construction cases. 1. **Local tree structure.** Reading the frontier of an elementary-tree fragment from left to right gives a linear tuple function. Terminals are written directly into the output, and substitution nodes contribute variables supplied by fan-out-one children. 2. **Substitution.** If an initial tree with yield $w$ substitutes at an $X\!\downarrow$ node, the variable for that node is replaced by $w$. This is ordinary one-component concatenation. 3. **Adjunction.** If an auxiliary derivation contributes $(u,v)$ and the derivation at the adjunction site contributes $w$, the translated rule returns $uwv$. If one auxiliary context $(u_1,v_1)$ adjoins inside another $(u_2,v_2)$, their combined context is $(u_2u_1,v_1v_2)$; placing $w$ in its gap yields $u_2u_1wv_1v_2$. We prove correctness by induction on the number of substitutions and adjunctions. Before either operation applies, every initial tree has the same one-component frontier yield in both grammars, and every auxiliary tree has the same pair of strings around its foot. This establishes the base cases. For the inductive step, suppose the invariant holds for the derived trees being combined. In a substitution step, both derivations replace the same frontier position by the same child yield. In an adjunction step, both derivations place the same site yield between the same left and right components. Thus, the resulting initial tree again has the same yield, or the resulting auxiliary tree again has the same context pair. At the start symbol there is no foot, so the LCFRS and TAG derive exactly the same terminal strings. Take an auxiliary tree whose frontier is schematically $\text{will}\;X^*\;\text{today}$. The translation records the pair $(\text{will},\text{today})$. If the $X$ subtree has yield *chase rabbits*, TAG adjunction produces *will chase rabbits today*. The LCFRS rule inserts the same site yield between the two components and produces that same string. Conversely, any use of this particular one-gap rule identifies the two surrounding components and the inserted $X$ yield, so it reconstructs the corresponding adjunction step. ### Why the converse needs a restriction An arbitrary fan-out-two LCFRS can combine pairs in ways that do not describe one context around one gap. It might cross or independently interleave the components of several children. A single TAG auxiliary tree cannot in general represent those arrangements. Thus, the preceding construction proves $$ \text{TAG languages}\subseteq\text{fan-out-two LCFRS languages}, $$ not equality with all fan-out-two LCFRSs. For the converse used in this characterization, restrict the LCFRS to the **root–foot normal form** produced by the construction above. In this normal form, a fan-out-two nonterminal always denotes one context around one gap, and every rule describes local tree structure, substitution, or insertion into that gap. This name is local to these notes; it identifies the image of the TAG compilation rather than every formalism called a well-nested fan-out-two LCFRS. We can now reverse the three cases. A fan-out-one rule becomes an initial-tree fragment; a paired nonterminal becomes an auxiliary-tree fragment whose root and foot share a label; and a function that inserts one yield between the two components of a context becomes adjunction. The rule restriction guarantees that these fragments can be arranged around one foot without crossing components. The reverse invariant is again the one-gap invariant. A derived pair $(u,v)$ corresponds to an auxiliary derived tree whose frontier is $uX^*v$, and a derived singleton $(w)$ corresponds to an initial derived tree with yield $w$. The base rules create the corresponding elementary fragments. Each one-gap tuple combination becomes either substitution or adjunction and preserves the invariant. This proves equality between TAG and the appropriately constrained fan-out-two system, while leaving the proper inclusion into unrestricted MCFG intact. ## The TAG $=$ HG $=$ LIG $=$ restricted-CCG construction guide The four-formalism theorem also includes head grammar (HG) [@vijayshanker1994equivalence]. We will first connect HG to the one-gap representation used for TAG and then use linear indexed grammar (LIG) to connect TAG with restricted CCG. ### TAG and HG A head grammar derives *headed strings*. Write one as $$\alpha\widehat{x}\beta,$$ where the marked terminal $x$ is the distinguished head. The visible yield is $\alpha x\beta$. For the translation, encode this headed string as the pair $$ (\alpha x,\beta). $$ The pair places a cut immediately after the head. This is an administrative cut, not a claim about the linguistic head of a TAG tree. Head grammars use concatenation and wrapping operations. Concatenation joins the visible yields of several headed strings and selects one of their heads as the head of the result. Wrapping is easier to see with two strings: $$ w(\alpha\widehat{x}\beta,\gamma\widehat{y}\delta) =\alpha x\gamma\widehat{y}\delta\beta. $$ Under the pair encoding, the two inputs are $(\alpha x,\beta)$ and $(\gamma y,\delta)$, and the output is $$ (\alpha x\gamma y,\delta\beta). $$ Thus, wrapping combines two pairs by concatenating their left components in forward order and their right components in reverse order. This is exactly the context-composition pattern used when one TAG auxiliary context is inserted into another. The head-grammar concatenation operations are also linear tuple functions: they concatenate every input yield once and place the output cut at the head selected by the operation. Translate each HG rule into the corresponding tuple rule. The invariant is: > HG nonterminal $A$ derives $\alpha\widehat{x}\beta$ if and only if its tuple translation derives $A(\alpha x,\beta)$. A terminal-only headed rule gives the same pair and establishes the base case. For the inductive step, assume the children satisfy the invariant. A concatenation rule applies the same left-to-right concatenation and retains the same selected cut in both representations. A wrapping rule applies the pair function just calculated. Thus, each HG derivation has a tuple derivation with the same visible yield. What about the reverse direction? We cannot simply turn *every* pair $(p,q)$ into a headed string. The encoding $(\alpha x,\beta)$ requires the left component to end in the distinguished head $x$; inventing an "empty head" would change the formalism and, unless it were removed by an additional construction, the string language. The full proof first normalizes the tuple rules so that every distinguished cut is anchored in this way. It then replaces the anchored cut with the corresponding head and checks the finite concatenation and wrapping cases one by one [@vijayshanker1994equivalence]. This anchoring condition is the missing reverse invariant: > A tuple configuration corresponds to an HG object only if its distinguished cut is licensed by the head annotation carried by that configuration. With that condition in place, a context-composition rule becomes wrapping, and an ordinary frontier combination becomes a head-grammar concatenation operation. The TAG and HG constructions can then be related through the same normalized one-gap representation. The pair calculation gives the wrapping case, while the anchoring and normal-form cases are needed for the full theorem. A small wrapping trace makes the anchored cut visible. Encode $\text{the}\;\widehat{\text{dog}}\;\text{today}$ as $(\text{the dog},\text{today})$ and $\text{will}\;\widehat{\text{run}}\;\text{now}$ as $(\text{will run},\text{now})$. Wrapping the second headed string inside the first gives $\text{the dog will}\;\widehat{\text{run}}\;\text{now today}$, whose pair is $(\text{the dog will run},\text{now today})$. The pair calculation preserves both the visible yield and the cut after *run*. The reverse construction works for this trace because that cut is anchored by the marked head; the general reverse direction requires the normalization just described. ### TAG and LIG A LIG attaches a stack of indices to a nonterminal, but only one child in a production inherits the active stack. We will call that child the *spine child*. Begin with the TAG-to-LIG direction. Every auxiliary tree has a unique path from its root to its foot. Treat this path as a spine. Entering an auxiliary tree pushes a symbol that identifies the pending material around the foot; following the root-to-foot path passes the stack to the next spine node; and completing the auxiliary tree pops that symbol after its off-spine subtrees have been derived. Substitution sites become ordinary context-free children because they do not carry the active stack. The invariant is: > A TAG derivation with a sequence of unfinished auxiliary trees along its active root-to-foot path corresponds to a LIG nonterminal whose index stack lists exactly those auxiliary trees in nesting order. With no unfinished adjunction, the stack is empty and an initial tree is simulated by ordinary productions. This is the base case. Adjoining one auxiliary tree adds one unfinished root-to-foot dependency, and the LIG pushes its index. Descending the spine leaves that index available while off-spine material is completed. Reaching the foot discharges the dependency, so the LIG pops the same index. Substitution does not affect the spine and thus leaves the stack unchanged. Induction on the TAG derivation proves that every TAG yield is a LIG yield. For the reverse direction, first normalize the LIG so that a production changes the stack by at most one symbol and still passes it to at most one child. Because only one child inherits the active stack, the stack-carrying nodes form a single spine through each relevant part of the derivation tree. For each compatible push and pop rule schema, create an auxiliary-tree template: the push site becomes its root, the pop site becomes its foot, and ordinary children become off-spine substitution sites. The possibly unbounded material between the two sites is produced recursively by further substitutions and adjunctions; it is not copied into one elementary tree. Stack-free productions become initial-tree fragments. The grammar has finitely many rules and stack symbols, so only finitely many templates are required. Now use the reverse invariant: the LIG stack records the auxiliary trees whose roots have been entered but whose feet have not yet been reached. A push starts adjunction, transmission follows the auxiliary spine, and the matching pop reaches the foot. Reading either derivation from left to right thus gives the same terminal yield. This establishes both containments between TAG and LIG. For a minimal trace, let $\beta$ be an auxiliary tree with schematic frontier $\text{will}\;X^*\;\text{today}$, and let the initial $X$ tree yield *run*. Entering $\beta$ changes the LIG stack from $[]$ to $[\beta]$. The stack is passed down the unique spine while *will* is produced off its left side. Reaching the foot matches the initial $X$ tree, produces *run*, and pops $\beta$; the remaining off-spine material produces *today*. Both derivations yield *will run today*. In the reverse direction, the matching push and pop delimit exactly the auxiliary-tree template for this example. ### LIG and restricted CCG A complex CCG category can be viewed as an atomic result together with a stack of unsatisfied arguments. For instance, $$ ((S\backslash NP)/NP)/PP $$ has atomic result $S$ and three pending arguments, with slash directions recording the sides on which they must be discharged. Under the restrictions in the equivalence theorem, application and bounded-degree composition inspect and modify only a bounded portion of this argument stack. Translate a restricted CCG category into a LIG nonterminal whose finite control records the bounded part of the category currently inspected by a combinator, and whose index stack records the unbounded remainder of its argument structure. A lexical category initializes that representation. Application removes the matching exposed argument. Composition transfers a bounded sequence of arguments from one category to another, which is simulated by a fixed sequence of LIG stack operations. Why is the translated grammar finite? There are finitely many lexical categories and combinator schemata, and the composition degree has a fixed bound. The finite control thus has only finitely many local cases to distinguish. The stack may be unbounded during a derivation, but its alphabet is drawn from the finite collection of argument records induced by those cases. An indexed grammar thus combines finitely many productions with an unbounded stack. The category-stack invariant states: > A CCG constituent with category $C$ and yield $w$ corresponds to a LIG constituent with yield $w$ whose finite control and stack encode exactly $C$. Lexical entries establish the invariant. Each licensed combinator has a corresponding LIG rule sequence that performs the same bounded category operation and concatenates the same left and right yields. Thus, induction on CCG derivations gives the CCG-to-LIG containment. For the reverse direction, first place the LIG in the restricted normal form used by the theorem. We then encode a stack symbol as one argument layer of a CCG category. A normalized push adds that layer; a normalized pop discharges it; and a rule that transmits the stack to the unique spine child becomes a bounded composition schema. Stack-free terminal and branching rules become lexical and application cases. Because the normalized LIG has finitely many rule and stack-symbol types, this construction produces a finite CCG grammar. Reading the category-stack invariant from LIG configurations to CCG categories gives the reverse simulation. The full proof checks each normalized LIG rule against its CCG schema; without that case list, "put the stack in the category" would only name the idea, not prove the containment. For instance, the familiar transitive-verb derivation illustrates the stack invariant. Treat $(S\backslash NP)/NP$ as result $S$ with a leftward $NP$ argument and a currently exposed rightward $NP$ argument. Combining it with the right-hand $NP$ in *chase rabbits* removes that exposed argument and leaves $S\backslash NP$. Combining the result with the left-hand $NP$ in *greyhounds chase rabbits* removes the remaining argument and leaves $S$. The corresponding normalized LIG operations pop the same two argument records in the same order while producing the same three-word yield. This trace illustrates application; bounded composition requires the additional finite rule cases supplied by the theorem. The rule-by-rule constructions in the cited theorem give $$ \text{TAG}=\text{HG}=\text{LIG}=\text{restricted CCG} $$ at the level of string languages. The restriction on CCG is part of the theorem. Adding arbitrary combinators would invalidate the finite list of LIG simulations used in the proof. ## The MG $=$ MCFG/LCFRS construction guide The MG equivalence again requires two constructions [@michaelis1998derivational; @michaelis2001transforming; @harkema2001parsing]. The main problem is movement: an MG expression may contain pronounced material that will occupy several separated positions in the final string. An MCFG tuple provides a direct representation of those pieces. ### From MG to MCFG Fix an MG of the kind treated by @michaelis1998derivational: its feature sets and lexicon are finite, features are checked from the left edge of their sequences, and the relevance condition permits at most one active maximal projection for each licensee feature. For every partial MG expression, record two kinds of information: 1. its remaining head-feature sequence and the feature types of its active movers; and 2. an $m+2$-tuple $(\pi_H,\pi_0,\ldots,\pi_m)$, separating the phonetic head material, the residual yield of the whole expression, and the residual pronounced material associated with each of the $m$ licensee types. The first record is a *configuration type*. There are only finitely many configuration types because the lexicon and feature inventory are finite and the movement condition bounds the mover store. Create one MCFG nonterminal for each type. Its fan-out is the number of strings in the corresponding tuple. The invariant is: > An MG expression of type $\tau$ with ordered yield pieces $\mathbf{w}$ exists if and only if the MCFG nonterminal $A_\tau$ derives the tuple $\mathbf{w}$. Lexical items establish the base case. A pronounced lexical item contributes its phonological string to the appropriate component; a silent item contributes $\epsilon$. Its unconsumed features determine $\tau$. There are then two inductive cases. 1. **Merge.** Suppose one expression begins with selector $=x$ and another supplies category $x$. Merge consumes the matching features and concatenates their head yields in the order fixed by the MG definition. Their mover stores are carried into the result. The corresponding MCFG rule takes the two child tuples, concatenates exactly the components joined by Merge, and passes every other component through once. 2. **Move.** Suppose an expression begins with licensor $+f$ and contains the uniquely matching mover with $-f$. Move consumes both features and places the mover yield in its pronounced position. The corresponding MCFG rule removes that yield from its mover component and concatenates it into the designated output component. Every string variable again occurs exactly once. In each case, the output configuration type is determined by the remaining features, and the tuple function reproduces the MG word order. Thus, the invariant is preserved. A complete MG expression has no unchecked features or active movers and has one terminal yield. The corresponding fan-out-one start nonterminal derives exactly that yield, proving the MG-to-MCFG containment. Consider a partial MG expression whose residual yield is *likes rabbits* and whose active $wh$ mover has yield *who*. Suppose the phonetic-head component and the slots for every other licensee type are empty. If we suppress those empty components, the relevant part of the tuple is $(\text{likes rabbits},\text{who})$. When a $+wh$ licensor matches the mover's $-wh$ feature, Move consumes the two features and places the mover before the residual yield, producing *who likes rabbits*. On the displayed components, the matching MCFG step applies $f(x,y)=yx$. Reading this step in reverse recovers which mover component was discharged, provided that the configuration type records the matching feature. ### From LCFRS to MG For the other direction, first replace the MCFG with a weakly equivalent LCFRS of rank at most two. Corollary 2.8 of @michaelis2001transforming [p. 231] guarantees this replacement; *rank at most two* means that each production has at most two nonterminal children. We can thus handle a finite set of local cases without changing the string language. Consider a binary production such as $$ A(x_1y_1,\;y_2x_2) \rightarrow B(x_1,x_2),C(y_1,y_2). $$ The MG translation gives the components supplied by $B$ and $C$ distinct movement features. It then performs three jobs: 1. lexical feature sequences identify the production and select encodings of its $B$ and $C$ children; 2. Merge places those encodings in one expression while their tuple components remain identifiable as movers; and 3. a fixed sequence of licensors exposes the pieces in the ledger order $x_1,y_1\mid y_2,x_2$, where the bar marks the boundary between the two output components specified by the LCFRS function. The vertical boundary between $x_1y_1$ and $y_2x_2$ is part of the package's bookkeeping. The sentence above does not mean that an intermediate MG expression has already pronounced the two fields as one contiguous string. Rather, the feature gadget keeps the fields distinguishable until a higher production consumes the package. The exact feature names are administrative. What matters is that the production is finite and linear: it mentions finitely many variables, and each variable occurs once. The MG can thus assign one licensee to each component and use a finite feature sequence to place each component exactly once. A constant terminal in the LCFRS function is supplied by a pronounced lexical item in the corresponding package. There are only finitely many such gadgets. The LCFRS has finitely many productions, and each production mentions finitely many component variables. We create a fixed lexical package for each production rather than a new lexical item for each derived tuple of strings. The strings themselves enter through the recursively selected child packages. The reverse invariant is: > An LCFRS derivation of $A(\mathbf{w})$ exists if and only if a complete MG production package of category $A$ has still-separated pronounced pieces, in the order named by the package, equal to $\mathbf{w}$. For the displayed LCFRS rule, suppose $B$ derives $(a,d)$ and $C$ derives $(b,c)$. Substitution gives $$ A(x_1y_1,y_2x_2)=A(ab,cd). $$ The MG production package selects the encodings of those two child tuples, keeps the four pieces identifiable, and discharges their licensees in the ledger order $a,b\mid c,d$. The resulting package thus records $(ab,cd)$ as well. Conversely, the lexical item that identifies this package determines the displayed LCFRS production, and the four discharged pieces determine its two child tuples. Constant productions establish the invariant with lexical packages. For the inductive step, assume that the packages for the child nonterminals encode the tuples derived by those children. The selector features for the parent production Merge those packages. Its licensors then Move the component yields into the order written by the LCFRS tuple function. Since the function is linear and nonerasing, no component is copied or lost. The resulting parent package thus encodes exactly the tuple derived by the LCFRS rule. This establishes the forward half of the invariant. For the reverse half, take a completed MG production package and inspect the lexical item that identifies its parent-production gadget. Its selector sequence requires packages of exactly the nonterminal types on the right side of that LCFRS production. Its movement features can discharge each component exactly once and only in the order specified by the tuple function. Decoding the child packages recursively thus reconstructs an LCFRS derivation with the same tuple. Induction on package height establishes both directions at the start symbol. The start symbol has fan-out one, so the completed MG package and the LCFRS derivation have the same terminal yield. ## Keeping the conclusions and proof status separate The arguments support three different conclusions, with different proof status in these notes: 1. We proved directly that fan-out-one MCFGs and CFGs generate the same string languages. 2. We proved directly that the MCFG and LCFRS notations used here describe the same linear, nonerasing tuple operations. 3. We traced the invariants behind the TAG–HG–LIG–restricted-CCG and MG–MCFG equivalence theorems. The cited sources prove the full results by checking the normal-form production cases that the construction guides summarize. These results do not collapse the entire unit into one class. In particular, $$ \text{CFG} \subsetneq \text{TAG} \subsetneq \text{MCFG}. $$ Nor do they say that corresponding derivations express the same linguistic analysis. The translations establish weak equivalence by preserving yields. Questions about elementary domains, derivation trees, lexicalization, and the interpretation of movement remain separate. ::: {.callout-caution} ## Question Suppose we have translated every TAG into a fan-out-two LCFRS with the same language. Have we proved that TAG and fan-out-two LCFRS are weakly equivalent? ::: ::: {.callout-tip collapse="true"} ## Answer No. We have proved only the TAG-to-LCFRS containment. Equality would require a reverse translation for every fan-out-two LCFRS, and that claim is false without restricting the LCFRS rules. Unrestricted fan-out-two systems can generate string languages outside the TAG class. :::