Bottom-Up Form of Top-Down Grammar defines same Formal Language

Theorem

Let $\mathcal L$ be a formal language.

Let $\mathcal T$ be a top-down grammar for $\mathcal L$.

Let $\mathcal B$ be the bottom-up form of $\mathcal T$.

Then $\mathcal B$ is also a formal grammar for $\mathcal L$.

Proof

Let $\phi$ be a $\mathcal B$-WFF.

If $\phi$ is a letter, then it is clearly a $\mathcal T$-WFF.

For, it may be formed by replacing the starting metasymbol of $\mathcal T$ by $\phi$.

Suppose that $\phi$ is formed from WFFs $\phi_1, \ldots, \phi_n$ by the rule of formation $\mathbf R_{\mathcal B}$ of $\mathcal B$.

Suppose also that each of $\phi_1, \ldots, \phi_n$ is also a $\mathcal T$-WFF.

Then by applying the rule of formation $\mathbf R$ of $\mathcal T$, we obtain a collation with metasymbols $\psi_1, \ldots, \psi_n$.

By assumption, we can apply rules of formation of $\mathcal T$ to each $\psi_i$ to yield the corresponding $\mathcal T$-WFF $\phi_i$.

It follows that $\phi$ is also a $\mathcal T$-WFF.

By the Principle of Structural Induction, each $\mathcal B$-WFF is also a $\mathcal T$-WFF.

Conversely, suppose that $\phi$ is a $\mathcal T$-WFF.

Let it be formed by applying the rules of formation $\mathbf R_1, \ldots, \mathbf R_n$, in succession.

We will prove that each metasymbol in the inputs of these rules of formation will be replaced by a $\mathcal B$-WFF.

In particular, then, $\phi$ will be a $\mathcal B$-WFF.

Since $\mathbf R_n$ is the last rule of formation applied, it must replace a metasymbol by a letter.

Since letters are $\mathcal B$-WFFs, $\mathbf R_n$ satisfies the assertion.

Suppose that we have established that all metasymbols in the result of $\mathbf R_i$ will be replaced by $\mathcal B$-WFFs.

Then also the metasymbol $\psi$ that $\mathbf R_i$ replaces by a new collation will be replaced by a WFF.

This is because the collation resulting from replacing $\psi$ according to $\mathbf R_i$ contains metasymbols $\psi_i$, which by assumption will be replaced by corresponding $\mathcal B$-WFFs $\phi_i$.

Now the rule of formation $\left({\mathbf R_i}\right)_{\mathcal B}$ ensures that $\psi$ will be replaced by a $\mathcal B$-WFF.

So each metasymbol $\psi$ in the input of $\mathbf R_i$ will be replaced by a $\mathcal B$-WFF.

Hence $\phi$ is a $\mathcal B$-WFF.

$\blacksquare$

Remark

This theorem establishes that any formal language has a bottom-up grammar.

We may therefore assume any formal language to be given by a bottom-up grammar, which provides conceptual simplicity.