Changes

It is fitting to wrap up the foregoing developments by summarizing the notion of a formal grammar that appeared to evolve in the present case.  For the sake of future reference and the chance of a wider application, it is also useful to try to extract the scheme of a formalization that potentially holds for any formal language.  The following presentation of the notion of a formal grammar is adapted, with minor modifications, from the treatment in (DDQ, 60–61).

It is fitting to wrap up the foregoing developments by summarizing the notion of a formal grammar that appeared to evolve in the present case.  For the sake of future reference and the chance of a wider application, it is also useful to try to extract the scheme of a formalization that potentially holds for any formal language.  The following presentation of the notion of a formal grammar is adapted, with minor modifications, from the treatment in (DDQ, 60–61).

A ''formal grammar'' <math>\mathfrak{G}</math> is given by a four-tuple <math>\mathfrak{G} = ( \, ^{\backprime\backprime} \, S \, ^{\prime\prime}, \, \mathfrak{Q}, \, \mathfrak{A}, \, \mathfrak{K} \, )</math> that takes the following form of description:

A ''formal grammar'' <math>\mathfrak{G}</math> is given by a four-tuple <math>\mathfrak{G} = ( \, ^{\backprime\backprime} S \, ^{\prime\prime}, \, \mathfrak{Q}, \, \mathfrak{A}, \, \mathfrak{K} \, )</math> that takes the following form of description:

<ol style="list-style-type:decimal">

<ol style="list-style-type:decimal">

</ol>

</ol>

To describe the elements of <math>\mathfrak{K}</math> it helps to define some additional terms:

To describe the elements of !K! it helps to define some additional terms:

 

a.  The symbols in {"S"} |_| !Q! |_| !A! form the "augmented alphabet" of !G!.

<li>The symbols in <math>\{ \, ^{\backprime\backprime} S \, ^{\prime\prime} \, \} \cup \mathfrak{Q} \cup \mathfrak{A}</math> form the ''augmented alphabet'' of <math>\mathfrak{G}.</math></li>

b.  The symbols in {"S"} |_| !Q! are the "non-terminal symbols" of !G!.

<li>The symbols in <math>\{ \, ^{\backprime\backprime} S \, ^{\prime\prime} \, \} \cup \mathfrak{Q}</math> are the ''non-terminal symbols'' of <math>\mathfrak{G}.</math></li>

c.  The symbols in !Q! |_| !A! are the "non-initial symbols" of !G!.

<li>The symbols in <math>\mathfrak{Q} \cup \mathfrak{A}</math> are the ''non-initial symbols'' of <math>\mathfrak{G}.</math></li>

d.  The strings in ({"S"} |_| !Q! |_| !A!)*  are the "augmented strings" for G.

<li>The strings in <math>( \{ \, ^{\backprime\backprime} S \, ^{\prime\prime} \, \} \cup \mathfrak{Q} \cup \mathfrak{A} )^*</math> are the ''augmented strings'' for <math>\mathfrak{G}.</math></li>

e.  The strings in {"S"} |_| (!Q! |_| !A!)* are the "sentential forms" for G.

<li>The strings in <math>\{ \, ^{\backprime\backprime} S \, ^{\prime\prime} \, \} \cup (\mathfrak{Q} \cup \mathfrak{A})^*</math> are the ''sentential forms'' for <math>\mathfrak{G}.</math></li>

Each characterization in !K! is an ordered pair of strings (S_1, S_2)

Each characterization in !K! is an ordered pair of strings (S_1, S_2)

that takes the following form:

that takes the following form: