Changes

With the foregoing array of considerations in mind, one is gradually led to a grammar for <math>\mathfrak{L} = \mathfrak{C} (\mathfrak{P})</math> in which all of the covering productions have either one of the following two forms:

With the foregoing array of considerations in mind, one is gradually led to a grammar for <math>\mathfrak{L} = \mathfrak{C} (\mathfrak{P})</math> in which all of the covering productions have either one of the following two forms:

{| align="center" cellpadding="8" width="%90"

{| align="center" cellpadding="8" width="90%"

|

|

<math>\begin{array}{ccll}

<math>\begin{array}{ccll}

|}

|}

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 q :> W, the replacement

string W 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 S :> e,

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 5 is a context-free grammar for the painted cactus language

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.

that uses !Q! = {"S'", "T"}, with !K! as listed in the next display.

===Grammar 5===

===Grammar 5===