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 ) = \emptyset $ 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 \rightarrow \alpha $, one defines

$$ \mu ( A \rightarrow \alpha ) = \left \{ {A ^ \prime \rightarrow \alpha ^ \prime } : {A ^ \prime \in \mu ( A ) \textrm{ and } \alpha ^ \prime \in \mu ( \alpha ) } \right \} . $$

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 \lhd G \pmod \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 ) = \left \{ {G ^ \prime } : {G ^ \prime \lhd G \pmod \mu \textrm{ for some } \mu } \right\} , $$

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

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

[a1]	A.B. Cremers, S. Ginsburg, "Context-free grammar forms" J. Comput. System Sci. , 11 (1975) pp. 86–116 MR0375848 Zbl 0328.68071
[a2]	H.A. Maurer, M. Penttonen, A. Salomaa, D. Wood, "On non context-free grammar forms" Math. Systems Th. , 12 (1979) pp. 297–324 MR0541861 Zbl 0415.68036
[a3]	A. Salomaa, H.A. Maurer, D. Wood, "Dense hierarchies of grammatical families" J. Assoc. Comput. Mach. , 29 (1982) pp. 118–126 MR0662614 Zbl 0491.68077
[a4]	V. Niemi, "Density of grammar forms, I; II" Internat. J. Comput. Math. , 20 (1986) pp. 3–21; 91–114 Zbl 0655.68098
[a5]	Gh. Păun, A. Salomaa, "Families generated by grammars and L systems" G. Rozenberg (ed.) A. Salomaa (ed.) , Handbook of Formal Languages , 1 , Springer (1997) pp. 811–861 MR1470004
[a6]	A. Salomaa, "On color-families of graphs" Ann. Acad. Sci. Fennicae , AI6 (1981) pp. 135–148 MR0639971 Zbl 0497.05027