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
How to Cite This Entry:
Grammar form. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Grammar_form&oldid=51118
This article was adapted from an original article by A. MateescuA. Salomaa (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article