View source for Grammar form

<!--
g1101801.png
$#A+1 = 41 n = 0
$#C+1 = 41 : ~/encyclopedia/old_files/data/G110/G.1100180 Grammar form
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A (phrase-structure) grammar (cf. also [[Grammar system|Grammar system]])  $  G = ( V _ {N} ,V _ {T} ,S,P ) $, 
viewed as a source of structurally similar grammars. (See [[Formal languages and automata|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|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 [[#References|[a5]]]. [[#References|[a1]]] and [[#References|[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 [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], and [[#References|[a6]]] for a connection with [[Graph colouring|graph colouring]].) A theory analogous to grammar forms has been developed also for parallel rewriting. (See [[L-systems| $  L $-
systems]], [[#References|[a5]]].)

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> A.B. Cremers, S. Ginsburg, "Context-free grammar forms" ''J. Comput. System Sci.'' , '''11''' (1975) pp. 86–116 {{MR|0375848}} {{ZBL|0328.68071}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> H.A. Maurer, M. Penttonen, A. Salomaa, D. Wood, "On non context-free grammar forms" ''Math. Systems Th.'' , '''12''' (1979) pp. 297–324 {{MR|0541861}} {{ZBL|0415.68036}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> A. Salomaa, H.A. Maurer, D. Wood, "Dense hierarchies of grammatical families" ''J. Assoc. Comput. Mach.'' , '''29''' (1982) pp. 118–126 {{MR|0662614}} {{ZBL|0491.68077}} </TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> V. Niemi, "Density of grammar forms, I; II" ''Internat. J. Comput. Math.'' , '''20''' (1986) pp. 3–21; 91–114 {{MR|}} {{ZBL|0655.68098}} </TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> 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 {{MR|1470004}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> A. Salomaa, "On color-families of graphs" ''Ann. Acad. Sci. Fennicae'' , '''AI6''' (1981) pp. 135–148 {{MR|0639971}} {{ZBL|0497.05027}} </TD></TR></table>