Namespaces
Variants
Actions

Difference between revisions of "Grammar form"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (MR/ZBL numbers added)
m (tex encoded by computer)
Line 1: Line 1:
A (phrase-structure) grammar (cf. also [[Grammar system|Grammar system]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g1101801.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g1101802.png" /> 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.
+
<!--
 +
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.
 +
-->
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g1101803.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g1101804.png" /> be alphabets. A disjoint-finite-letter substitution (dfl-substitution) is a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g1101805.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g1101806.png" /> into the set of non-empty subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g1101807.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g1101808.png" /> for all distinct <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g1101809.png" />. Thus, a dfl-substitution associates one or more letters of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018010.png" /> to each letter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018011.png" />, and no letter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018012.png" /> is associated to two letters of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018013.png" />. Because <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018014.png" /> is a substitution, its domain is immediately extended to concern words and languages over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018015.png" />. For a production <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018016.png" />, one defines
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018017.png" /></td> </tr></table>
+
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.
  
A grammar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018018.png" /> is an interpretation of a grammar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018019.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018020.png" />, denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018021.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018022.png" /> is a dfl-substitution on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018023.png" />, if the following conditions are satisfied:
+
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
  
i) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018026.png" />;
+
$$
 +
\mu ( A \rightarrow \alpha ) = \left \{ {A  ^  \prime  \rightarrow \alpha  ^  \prime  } : {A  ^  \prime  \in \mu ( A )  \textrm{ and }  \alpha  ^  \prime  \in \mu ( \alpha ) } \right \} .
 +
$$
  
ii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018027.png" />. The grammar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018028.png" /> is referred to as the master or form grammar, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018029.png" /> is the image or interpretation grammar. The grammar family and the grammatical (language) family of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018030.png" /> are defined by
+
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  riangle\left G ( { \mathop{\rm mod} } \mu ) \right .$,
 +
where  $  \mu $
 +
is a dfl-substitution on  $  V _ {N} $,
 +
if the following conditions are satisfied:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018031.png" /></td> </tr></table>
+
i)  $  V _ {N}  ^  \prime  = \mu ( V _ {N} ) $,
 +
$  V _ {T}  ^  \prime  = \mu ( V _ {T} ) $
 +
and  $  S  ^  \prime  \in \mu ( S ) $;
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018032.png" /></td> </tr></table>
+
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
  
A language family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018033.png" /> is termed grammatical if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018034.png" />, for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018035.png" />. Two grammars are form equivalent if their language families coincide. They are strongly form-equivalent if their grammar families coincide.
+
$$
 +
{\mathcal G} ( G ) = \left \{ {G  ^  \prime  } : {G  ^  \prime  riangle\left G ( { \mathop{\rm mod} } \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.
 
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.
Line 23: Line 72:
 
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.)
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018036.png" /> is a grammatical family containing all regular languages and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018037.png" /> is a grammatical family such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018038.png" />, then there is a grammatical family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018039.png" /> with the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018040.png" />. (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|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110180/g11018041.png" />-systems]], [[#References|[a5]]].)
+
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====
 
====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>
 
<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>

Revision as of 19:42, 5 June 2020


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 riangle\left G ( { \mathop{\rm mod} } \mu ) \right .$, 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 riangle\left G ( { \mathop{\rm mod} } \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=24458
This article was adapted from an original article by A. MateescuA. Salomaa (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article