Changes

<math>\mathfrak{C} (\mathfrak{P}) : \text{Grammar 2}\!</math>

<math>\mathfrak{C} (\mathfrak{P}) : \text{Grammar 2}\!</math>

| align="right" style="border-right:1px solid black;" width="50%" |

| align="right" style="border-right:1px solid black;" width="50%" |

<math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} \, T \, ^{\prime\prime} \, \}</math>

<math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} T \, ^{\prime\prime} \, \}</math>

|-

|-

| colspan="2" style="border-top:1px solid black; border-bottom:1px solid black; border-left:1px solid black; border-right:1px solid black" |

| colspan="2" style="border-top:1px solid black; border-bottom:1px solid black; border-left:1px solid black; border-right:1px solid black" |

In this rendition, a string of type <math>T\!</math> is not in general a sentence itself but a proper ''part of speech'', that is, a strictly ''lesser'' component of a sentence in any suitable ordering of sentences and their components.  In order to see how the grammatical category <math>T\!</math> gets off the ground, that is, to detect its minimal strings and to discover how its ensuing generations get started from these, it is useful to observe that the covering rule <math>T :> S\!</math> means that <math>T\!</math> ''inherits'' all of the initial conditions of <math>S,\!</math> namely, <math>T \, :> \, \varepsilon, m_1, p_j.</math>  In accord with these simple beginnings it comes to parse that the rule <math>T \, :> \, T \, \cdot \, ^{\backprime\backprime} \operatorname{,} ^{\prime\prime} \, \cdot \, S,</math> with the substitutions <math>T = \varepsilon</math> and <math>S = \varepsilon</math> on the covered side of the rule, bears the germinal implication that <math>T \, :> \, ^{\backprime\backprime} \operatorname{,} ^{\prime\prime}.</math>

In this rendition, a string of type <math>T\!</math> is not in general a sentence itself but a proper ''part of speech'', that is, a strictly ''lesser'' component of a sentence in any suitable ordering of sentences and their components.  In order to see how the grammatical category <math>T\!</math> gets off the ground, that is, to detect its minimal strings and to discover how its ensuing generations get started from these, it is useful to observe that the covering rule <math>T :> S\!</math> means that <math>T\!</math> ''inherits'' all of the initial conditions of <math>S,\!</math> namely, <math>T \, :> \, \varepsilon, m_1, p_j.</math>  In accord with these simple beginnings it comes to parse that the rule <math>T \, :> \, T \, \cdot \, ^{\backprime\backprime} \operatorname{,} ^{\prime\prime} \, \cdot \, S,</math> with the substitutions <math>T = \varepsilon</math> and <math>S = \varepsilon</math> on the covered side of the rule, bears the germinal implication that <math>T \, :> \, ^{\backprime\backprime} \operatorname{,} ^{\prime\prime}.</math>

Grammar&nbsp;2 achieves a portion of its success through a higher degree of intermediate organization.  Roughly speaking, the level of organization can be seen as reflected in the cardinality of the intermediate alphabet <math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} T ^{\prime\prime} \, \}</math> but it is clearly not explained by this simple circumstance alone, since it is taken for granted that the intermediate symbols serve a purpose, a purpose that is easily recognizable but that may not be so easy to pin down and to specify exactly.  Nevertheless, it is worth the trouble of exploring this aspect of organization and this direction of development a little further.

Grammar&nbsp;2 achieves a portion of its success through a higher degree of intermediate organization.  Roughly speaking, the level of organization can be seen as reflected in the cardinality of the intermediate alphabet <math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} T \, ^{\prime\prime} \, \}</math> but it is clearly not explained by this simple circumstance alone, since it is taken for granted that the intermediate symbols serve a purpose, a purpose that is easily recognizable but that may not be so easy to pin down and to specify exactly.  Nevertheless, it is worth the trouble of exploring this aspect of organization and this direction of development a little further.

===Grammar 3===

===Grammar 3===

===Grammar 4===

===Grammar 4===

If one imposes the distinction between empty and significant types on each non-terminal symbol in Grammar&nbsp;2, then the non-terminal symbols <math>^{\backprime\backprime} S ^{\prime\prime}</math> and <math>^{\backprime\backprime} T ^{\prime\prime}</math> give rise to the expanded set of non-terminal symbols <math>^{\backprime\backprime} S ^{\prime\prime}, \, ^{\backprime\backprime} \, S' \, ^{\prime\prime}, \, ^{\backprime\backprime} T ^{\prime\prime}, \, ^{\backprime\backprime} \, T' \, ^{\prime\prime},</math> leaving the last three of these to form the new intermediate alphabet.  Grammar&nbsp;4 has the intermediate alphabet <math>\mathfrak{Q} \, = \, \{ \, ^{\backprime\backprime} \, S' \, ^{\prime\prime}, \, ^{\backprime\backprime} \, T \, ^{\prime\prime}, \, ^{\backprime\backprime} \, T' \, ^{\prime\prime} \, \},</math> with the set <math>\mathfrak{K}</math> of covering rules as listed in the next display.

If one imposes the distinction between empty and significant types on each non-terminal symbol in Grammar&nbsp;2, then the non-terminal symbols <math>^{\backprime\backprime} S \, ^{\prime\prime}</math> and <math>^{\backprime\backprime} T \, ^{\prime\prime}</math> give rise to the expanded set of non-terminal symbols <math>^{\backprime\backprime} S \, ^{\prime\prime}, \, ^{\backprime\backprime} S' \, ^{\prime\prime}, \, ^{\backprime\backprime} T \, ^{\prime\prime}, \, ^{\backprime\backprime} T' \, ^{\prime\prime},</math> leaving the last three of these to form the new intermediate alphabet.  Grammar&nbsp;4 has the intermediate alphabet <math>\mathfrak{Q} \, = \, \{ \, ^{\backprime\backprime} S' \, ^{\prime\prime}, \, ^{\backprime\backprime} T \, ^{\prime\prime}, \, ^{\backprime\backprime} T' \, ^{\prime\prime} \, \},</math> with the set <math>\mathfrak{K}</math> of covering rules as listed in the next display.

<br>

<br>

<math>\mathfrak{C} (\mathfrak{P}) : \text{Grammar 4}\!</math>

<math>\mathfrak{C} (\mathfrak{P}) : \text{Grammar 4}\!</math>

| align="right" style="border-right:1px solid black;" width="50%" |

| align="right" style="border-right:1px solid black;" width="50%" |

<math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} \, S' \, ^{\prime\prime}, \, ^{\backprime\backprime} \, T \, ^{\prime\prime}, \, ^{\backprime\backprime} \, T' \, ^{\prime\prime} \, \}</math>

<math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} S' \, ^{\prime\prime}, \, ^{\backprime\backprime} T \, ^{\prime\prime}, \, ^{\backprime\backprime} T' \, ^{\prime\prime} \, \}</math>

|-

|-

| colspan="2" style="border-top:1px solid black; border-bottom:1px solid black; border-left:1px solid black; border-right:1px solid black" |

| colspan="2" style="border-top:1px solid black; border-bottom:1px solid black; border-left:1px solid black; border-right:1px solid black" |

There does not appear to be anything radically wrong with trying this approach to types.  It is reasonable and consistent in its underlying principle, and it provides a rational and a homogeneous strategy toward all parts of speech, but it does require an extra amount of conceptual overhead, in that every non-trivial type has to be split into two parts and comprehended in two stages.  Consequently, in view of the largely practical difficulties of making the requisite distinctions for every intermediate symbol, it is a common convention, whenever possible, to restrict intermediate types to covering exclusively non-empty strings.

There does not appear to be anything radically wrong with trying this approach to types.  It is reasonable and consistent in its underlying principle, and it provides a rational and a homogeneous strategy toward all parts of speech, but it does require an extra amount of conceptual overhead, in that every non-trivial type has to be split into two parts and comprehended in two stages.  Consequently, in view of the largely practical difficulties of making the requisite distinctions for every intermediate symbol, it is a common convention, whenever possible, to restrict intermediate types to covering exclusively non-empty strings.

For the sake of future reference, it is convenient to refer to this restriction on intermediate symbols as the ''intermediate significance'' constraint.  It can be stated in a compact form as a condition on the relations between non-terminal symbols <math>q \in \{ \, ^{\backprime\backprime} S ^{\prime\prime} \, \} \cup \mathfrak{Q}</math> and sentential forms <math>W \in \{ \, ^{\backprime\backprime} S ^{\prime\prime} \, \} \cup (\mathfrak{Q} \cup \mathfrak{A})^*.</math>

For the sake of future reference, it is convenient to refer to this restriction on intermediate symbols as the ''intermediate significance'' constraint.  It can be stated in a compact form as a condition on the relations between non-terminal symbols <math>q \in \{ \, ^{\backprime\backprime} S \, ^{\prime\prime} \, \} \cup \mathfrak{Q}</math> and sentential forms <math>W \in \{ \, ^{\backprime\backprime} S \, ^{\prime\prime} \, \} \cup (\mathfrak{Q} \cup \mathfrak{A})^*.</math>

<br>

<br>

& q

& q

& =

& =

& ^{\backprime\backprime} \, S \, ^{\prime\prime}

& ^{\backprime\backprime} S \, ^{\prime\prime}

\\

\\

\end{array}</math>

\end{array}</math>

If this is beginning to sound like a monotone condition, then it is not absurd to sharpen the resemblance and render the likeness more acute.  This is done by declaring a couple of ordering relations, denoting them under variant interpretations by the same sign, <math>^{\backprime\backprime}\!< \, ^{\prime\prime}.</math>

If this is beginning to sound like a monotone condition, then it is not absurd to sharpen the resemblance and render the likeness more acute.  This is done by declaring a couple of ordering relations, denoting them under variant interpretations by the same sign, <math>^{\backprime\backprime}\!< \, ^{\prime\prime}.</math>

# The ordering <math>^{\backprime\backprime}\!< \, ^{\prime\prime}</math> on the set of non-terminal symbols, <math>q \in \{ \, ^{\backprime\backprime} \, S \, ^{\prime\prime} \, \} \cup \mathfrak{Q},</math> ordains the initial symbol <math>^{\backprime\backprime} \, S \, ^{\prime\prime}</math> to be strictly prior to every intermediate symbol.  This is tantamount to the axiom that <math>^{\backprime\backprime} \, S \, ^{\prime\prime} < q,</math> for all <math>q \in \mathfrak{Q}.</math>

# The ordering <math>^{\backprime\backprime}\!< \, ^{\prime\prime}</math> on the set of non-terminal symbols, <math>q \in \{ \, ^{\backprime\backprime} S \, ^{\prime\prime} \, \} \cup \mathfrak{Q},</math> ordains the initial symbol <math>^{\backprime\backprime} S \, ^{\prime\prime}</math> to be strictly prior to every intermediate symbol.  This is tantamount to the axiom that <math>^{\backprime\backprime} S \, ^{\prime\prime} < q,</math> for all <math>q \in \mathfrak{Q}.</math>

# The ordering <math>^{\backprime\backprime}\!< \, ^{\prime\prime}</math> on the collection of sentential forms, <math>W \in \{ \, ^{\backprime\backprime} \, S \, ^{\prime\prime} \, \} \cup (\mathfrak{Q} \cup \mathfrak{A})^*,</math> ordains the empty string to be strictly minor to every other sentential form.  This is stipulated in the axiom that <math>\varepsilon < W,</math> for every non-empty sentential form <math>W.\!</math>

# The ordering <math>^{\backprime\backprime}\!< \, ^{\prime\prime}</math> on the collection of sentential forms, <math>W \in \{ \, ^{\backprime\backprime} S \, ^{\prime\prime} \, \} \cup (\mathfrak{Q} \cup \mathfrak{A})^*,</math> ordains the empty string to be strictly minor to every other sentential form.  This is stipulated in the axiom that <math>\varepsilon < W,</math> for every non-empty sentential form <math>W.\!</math>

Given these two orderings, the constraint in question on intermediate significance can be stated as follows:

Given these two orderings, the constraint in question on intermediate significance can be stated as follows:

& q

& q

& >

& >

& ^{\backprime\backprime} \, S \, ^{\prime\prime}

& ^{\backprime\backprime} S \, ^{\prime\prime}

\\

\\

\text{then}

\text{then}

& :>

& :>

& W,

& W,

& \text{with} \ q \in \{ \, ^{\backprime\backprime} \, S \, ^{\prime\prime} \, \} \cup \mathfrak{Q} \ \text{and} \ W \in (\mathfrak{Q} \cup \mathfrak{A})^+

& \text{with} \ q \in \{ \, ^{\backprime\backprime} S \, ^{\prime\prime} \, \} \cup \mathfrak{Q} \ \text{and} \ W \in (\mathfrak{Q} \cup \mathfrak{A})^+

\\

\\

\end{array}</math>

\end{array}</math>

A grammar that fits into this mold is called a ''context-free grammar''.  The first type of rewrite rule is referred to as a ''special production'', while the second type of rewrite rule is called an ''ordinary production''.  An ''ordinary derivation'' is one that employs only ordinary productions.  In ordinary productions, those that have the form <math>q :> W,\!</math> the replacement string <math>W\!</math> is never the empty string, and so the lengths of the augmented strings or the sentential forms that follow one another in an ordinary derivation, on account of using the ordinary types of rewrite rules, never decrease at any stage of the process, up to and including the terminal string that is finally generated by the grammar.  This type of feature is known as the ''non-contracting property'' of productions, derivations, and grammars.  A grammar is said to have the property if all of its covering productions, with the possible exception of <math>S :> \varepsilon,</math> are non-contracting.  In particular, context-free grammars are special cases of non-contracting grammars.  The presence of the non-contracting property within a formal grammar makes the length of the augmented string available as a parameter that can figure into mathematical inductions and motivate recursive proofs, and this handle on the generative process makes it possible to establish the kinds of results about the generated language that are not easy to achieve in more general cases, nor by any other means even in these brands of special cases.

A grammar that fits into this mold is called a ''context-free grammar''.  The first type of rewrite rule is referred to as a ''special production'', while the second type of rewrite rule is called an ''ordinary production''.  An ''ordinary derivation'' is one that employs only ordinary productions.  In ordinary productions, those that have the form <math>q :> W,\!</math> the replacement string <math>W\!</math> is never the empty string, and so the lengths of the augmented strings or the sentential forms that follow one another in an ordinary derivation, on account of using the ordinary types of rewrite rules, never decrease at any stage of the process, up to and including the terminal string that is finally generated by the grammar.  This type of feature is known as the ''non-contracting property'' of productions, derivations, and grammars.  A grammar is said to have the property if all of its covering productions, with the possible exception of <math>S :> \varepsilon,</math> are non-contracting.  In particular, context-free grammars are special cases of non-contracting grammars.  The presence of the non-contracting property within a formal grammar makes the length of the augmented string available as a parameter that can figure into mathematical inductions and motivate recursive proofs, and this handle on the generative process makes it possible to establish the kinds of results about the generated language that are not easy to achieve in more general cases, nor by any other means even in these brands of special cases.

Grammar&nbsp;5 is a context-free grammar for the painted cactus language that uses <math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} \, S' \, ^{\prime\prime}, \, ^{\backprime\backprime} \, T \, ^{\prime\prime} \, \},</math> with <math>\mathfrak{K}</math> as listed in the next display.

Grammar&nbsp;5 is a context-free grammar for the painted cactus language that uses <math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} S' \, ^{\prime\prime}, \, ^{\backprime\backprime} T \, ^{\prime\prime} \, \},</math> with <math>\mathfrak{K}</math> as listed in the next display.

<br>

<br>

<math>\mathfrak{C} (\mathfrak{P}) : \text{Grammar 5}\!</math>

<math>\mathfrak{C} (\mathfrak{P}) : \text{Grammar 5}\!</math>

| align="right" style="border-right:1px solid black;" width="50%" |

| align="right" style="border-right:1px solid black;" width="50%" |

<math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} \, S' \, ^{\prime\prime}, \, ^{\backprime\backprime} \, T \, ^{\prime\prime} \, \}</math>

<math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} S' \, ^{\prime\prime}, \, ^{\backprime\backprime} T \, ^{\prime\prime} \, \}</math>

|-

|-

| colspan="2" style="border-top:1px solid black; border-bottom:1px solid black; border-left:1px solid black; border-right:1px solid black" |

| colspan="2" style="border-top:1px solid black; border-bottom:1px solid black; border-left:1px solid black; border-right:1px solid black" |

===Grammar 6===

===Grammar 6===

Grammar&nbsp;6 has the intermediate alphabet <math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} \, S' \, ^{\prime\prime}, \, ^{\backprime\backprime} \, F \, ^{\prime\prime}, \, ^{\backprime\backprime} \, R \, ^{\prime\prime}, \, ^{\backprime\backprime} \, T \, ^{\prime\prime} \, \},</math> with the production set <math>\mathfrak{K}</math> as listed in the next display.

Grammar&nbsp;6 has the intermediate alphabet <math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} S' \, ^{\prime\prime}, \, ^{\backprime\backprime} F \, ^{\prime\prime}, \, ^{\backprime\backprime} R \, ^{\prime\prime}, \, ^{\backprime\backprime} T \, ^{\prime\prime} \, \},</math> with the production set <math>\mathfrak{K}</math> as listed in the next display.

<br>

<br>

<math>\mathfrak{C} (\mathfrak{P}) : \text{Grammar 6}\!</math>

<math>\mathfrak{C} (\mathfrak{P}) : \text{Grammar 6}\!</math>

| align="right" style="border-right:1px solid black;" width="50%" |

| align="right" style="border-right:1px solid black;" width="50%" |

<math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} \, S' \, ^{\prime\prime}, \, ^{\backprime\backprime} \, F \, ^{\prime\prime}, \, ^{\backprime\backprime} \, R \, ^{\prime\prime}, \, ^{\backprime\backprime} \, T \, ^{\prime\prime} \, \}</math>

<math>\mathfrak{Q} = \{ \, ^{\backprime\backprime} S' \, ^{\prime\prime}, \, ^{\backprime\backprime} F \, ^{\prime\prime}, \, ^{\backprime\backprime} R \, ^{\prime\prime}, \, ^{\backprime\backprime} T \, ^{\prime\prime} \, \}</math>

|-

|-

| colspan="2" style="border-top:1px solid black; border-bottom:1px solid black; border-left:1px solid black; border-right:1px solid black" |

| colspan="2" style="border-top:1px solid black; border-bottom:1px solid black; border-left:1px solid black; border-right:1px solid black" |