Definition:Unique Parsability

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\mathcal L$ be a formal language.

Let every WFF of $\mathcal L$ result from a unique rule of formation.


Then $\mathcal L$ has unique parsability.


Bottom-Up Grammar

For a bottom-up grammar, a WFF $\phi$ results from a unique rule of formation iff:

$\phi$ results from applying the rule of formation $\mathbf R$ to WFFs $\phi_1, \ldots \phi_n$
$\phi$ results from applying the rule of formation $\mathbf R'$ WFFs $\psi_1, \ldots \psi_m$

imply that $\mathbf R = \mathbf R'$, $m = n$, and for $i = 1, \ldots, n$, $\phi_i = \psi_i$.


Top-Down Grammar

For a top-down grammar, a WFF $\phi$ results from a unique rule of formation iff:

$\phi$ results from applying the rule of formation $\mathbf R$, substituting the WFFs $\phi_1, \ldots, \phi_n$ for the metasymbols of $\mathbf R$
$\phi$ results from applying the rule of formation $\mathbf R'$, substituting the WFFs $\psi_1, \ldots, \psi_n$ for the metasymbols of $\mathbf R'$

imply that $\mathbf R = \mathbf R'$, $m = n$, and for $i = 1, \ldots, n$, $\phi_i = \psi_i$.