Definition:Bottom-Up Form of Top-Down Grammar

From ProofWiki
Jump to: navigation, search


Let $\mathcal L$ be a formal language.

Let $\mathcal L$ be given by a top-down formal grammar $\mathcal T$.

The bottom-up form of $\mathcal T$ is the formal grammar $\mathcal B$ defined by declaring that:

Each letter of $\mathcal L$ is a $\mathcal B$-WFF

and, for each rule of formation $\mathbf R$ of $\mathcal T$ of the form:

A metasymbol may be replaced by the collation $\phi$ with metasymbols $\phi_1, \ldots, \phi_n$

declaring that $\mathcal B$ has the rule of formation $\mathbf R_{\mathcal B}$:

If $\phi_1, \ldots, \phi_n$ are $\mathcal B$-WFFs, so is $\phi$.

Also see