Grammar form

A (phrase-structure) grammar (cf. also Grammar system) $G=(V_N,V_T,S,P)$, viewed as a source of structurally similar grammars. (See Formal languages and automata.) The languages generated by the latter grammars give rise to a family $\mathcal{L}(G)$ of languages. (See also Abstract family of languages.) Grammars viewed in this fashion, as generators of structurally similar grammars and their languages, are referred to as grammar forms.

Let $V_1$ and $V_2$ be alphabets. A disjoint-finite-letter substitution (dfl-substitution) is a mapping $\mu$ of $V_1$ into the set of non-empty subsets of $V_2$ such that $\mu (a)\cap \mu (b)=\mathrm{\varnothing }$ for all distinct $a,b\in V_1$. Thus, a dfl-substitution associates one or more letters of $V_2$ to each letter of $V_1$, and no letter of $V_2$ is associated to two letters of $V_1$. Because $\mu$ is a substitution, its domain is immediately extended to concern words and languages over $V_1$. For a production $A\to \alpha$, one defines

$$\mu (A\to \alpha )=\{A^{\prime }\to {\alpha }^{\prime }:A^{\prime }\in \mu (A)\text{ and }{\alpha }^{\prime }\in \mu (\alpha )\}.$$

A grammar $G^{\prime }=(V_N^{\prime },V_T^{\prime },S^{\prime },P^{\prime })$ is an interpretation of a grammar $G=(V_N,V_T,S,P)$ modulo $\mu$, denoted by $G^{\prime }⊲G(\mathrm{mod}\mu )$, where $\mu$ is a dfl-substitution on $V_N$, if the following conditions are satisfied:

i) $V_N^{\prime }=\mu (V_N)$, $V_T^{\prime }=\mu (V_T)$ and $S^{\prime }\in \mu (S)$;

ii) $P^{\prime }\subseteq \mu (P)={\cup }_{p\in P}\mu (p)$. The grammar $G$ is referred to as the master or form grammar, while $G^{\prime }$ is the image or interpretation grammar. The grammar family and the grammatical (language) family of $G$ are defined by

$$\mathcal{G}(G)=\{G^{\prime }:G^{\prime }⊲G(\mathrm{mod}\mu )\text{ for some }\mu \},$$

$$\mathcal{L}(G)=\{L(G^{\prime }):G^{\prime }\in \mathcal{G}(G)\}.$$

A language family $\mathcal{L}$ is termed grammatical if $\mathcal{L}=\mathcal{L}(G)$, for some $G$. Two grammars are form equivalent if their language families coincide. They are strongly form-equivalent if their grammar families coincide.

Operationally one obtains an interpretation grammar by mapping terminals and non-terminals of the form grammar into disjoint sets of terminals and non-terminals, respectively, then extending the mapping to concern productions and, finally, taking a subset of the resulting production set. The last-mentioned point is especially important: great flexibility results because it is possible to omit productions.

A grammar is said to be a grammar form if it is used within the framework of interpretations. There is no difference between a grammar and a grammar form as constructs.

Strong form equivalence is decidable, whereas form equivalence is undecidable even for context-free grammar forms. To characterize the grammar forms giving rise to a specific language family, e.g., the family of context-free languages, is equivalent to characterizing all possible normal forms for the corresponding grammars, e.g., all possible normal forms for context-free grammars. (For further details, see [a5]. [a1] and [a2] represent early developments.)

In spite of the discrete framework of formal languages, grammatical families possess remarkable density properties. For instance, if ${\mathcal{L}}_1$ is a grammatical family containing all regular languages and ${\mathcal{L}}_2$ is a grammatical family such that ${\mathcal{L}}_1\subset {\mathcal{L}}_2$, then there is a grammatical family ${\mathcal{L}}_3$ with the property ${\mathcal{L}}_1\subset {\mathcal{L}}_3\subset {\mathcal{L}}_2$. (See [a3], [a4], [a5], and [a6] for a connection with graph colouring.) A theory analogous to grammar forms has been developed also for parallel rewriting. (See $L$- systems, [a5].)

References[edit]