Cactus Language • Part 2

Author: Jon Awbrey

---

• Overview • Part 1 • Part 2 • Part 3 • References • Document History •

---

The Cactus Patch (cont.)

Generalities About Formal Grammars

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 ${\mathfrak {G}}$ is given by a four-tuple ${\mathfrak {G}}=(\,^{\backprime \backprime }S\,^{\prime \prime },\,{\mathfrak {Q}},\,{\mathfrak {A}},\,{\mathfrak {K}}\,)$ that takes the following form of description:

1. $^{\backprime \backprime }S\,^{\prime \prime }$ is the initial, special, start, or sentence symbol. Since the letter $^{\backprime \backprime }S\,^{\prime \prime }$ serves this function only in a special setting, its employment in this role need not create any confusion with its other typical uses as a string variable or as a sentence variable.
2. ${\mathfrak {Q}}=\{q_{1},\ldots ,q_{m}\}$ is a finite set of intermediate symbols, all distinct from $^{\backprime \backprime }S\,^{\prime \prime }.$
3. ${\mathfrak {A}}=\{a_{1},\dots ,a_{n}\}$ is a finite set of terminal symbols, also known as the alphabet of ${\mathfrak {G}},$ all distinct from $^{\backprime \backprime }S\,^{\prime \prime }$ and disjoint from ${\mathfrak {Q}}.$ Depending on the particular conception of the language ${\mathfrak {L}}$ that is covered, generated, governed, or ruled by the grammar ${\mathfrak {G}},$ that is, whether ${\mathfrak {L}}$ is conceived to be a set of words, sentences, paragraphs, or more extended structures of discourse, it is usual to describe ${\mathfrak {A}}$ as the alphabet, lexicon, vocabulary, liturgy, or phrase book of both the grammar ${\mathfrak {G}}$ and the language ${\mathfrak {L}}$ that it regulates.
4. ${\mathfrak {K}}$ is a finite set of characterizations. Depending on how they come into play, these are variously described as covering rules, formations, productions, rewrite rules, subsumptions, transformations, or typing rules.

To describe the elements of ${\mathfrak {K}}$ it helps to define some additional terms:

1. The symbols in $\{\,^{\backprime \backprime }S\,^{\prime \prime }\,\}\cup {\mathfrak {Q}}\cup {\mathfrak {A}}$ form the augmented alphabet of ${\mathfrak {G}}.$
2. The symbols in $\{\,^{\backprime \backprime }S\,^{\prime \prime }\,\}\cup {\mathfrak {Q}}$ are the non-terminal symbols of ${\mathfrak {G}}.$
3. The symbols in ${\mathfrak {Q}}\cup {\mathfrak {A}}$ are the non-initial symbols of ${\mathfrak {G}}.$
4. The strings in $(\{\,^{\backprime \backprime }S\,^{\prime \prime }\,\}\cup {\mathfrak {Q}}\cup {\mathfrak {A}})^{*}$ are the augmented strings for ${\mathfrak {G}}.$
5. The strings in $\{\,^{\backprime \backprime }S\,^{\prime \prime }\,\}\cup ({\mathfrak {Q}}\cup {\mathfrak {A}})^{*}$ are the sentential forms for ${\mathfrak {G}}.$

Each characterization in ${\mathfrak {K}}$ is an ordered pair of strings $(S_{1},S_{2})$ that takes the following form:

$S_{1}\ =\ Q_{1}\cdot q\cdot Q_{2},$

$S_{2}\ =\ Q_{1}\cdot W\cdot Q_{2}.$

In this scheme, $S_{1}$ and $S_{2}$ are members of the augmented strings for ${\mathfrak {G}},$ more precisely, $S_{1}$ is a non-empty string and a sentential form over ${\mathfrak {G}},$ while $S_{2}$ is a possibly empty string and also a sentential form over ${\mathfrak {G}}.$

Here also, $q$ is a non-terminal symbol, that is, $q\in \{\,^{\backprime \backprime }S\,^{\prime \prime }\,\}\cup {\mathfrak {Q}},$ while $Q_{1},Q_{2},$ and $W$ are possibly empty strings of non-initial symbols, a fact that can be expressed in the form, $Q_{1},Q_{2},W\in ({\mathfrak {Q}}\cup {\mathfrak {A}})^{*}.$

In practice, the couplets in ${\mathfrak {K}}$ are used to derive, to generate, or to produce sentences of the corresponding language ${\mathfrak {L}}={\mathfrak {L}}({\mathfrak {G}}).$ The language ${\mathfrak {L}}$ is then said to be governed, licensed, or regulated by the grammar ${\mathfrak {G}},$ a circumstance that is expressed in the form ${\mathfrak {L}}=\langle {\mathfrak {G}}\rangle .$ In order to facilitate this active employment of the grammar, it is conventional to write the abstract characterization $(S_{1},S_{2})$ and the specific characterization $(Q_{1}\cdot q\cdot Q_{2},\ Q_{1}\cdot W\cdot Q_{2})$ in the following forms, respectively:

${\begin{array}{lll}S_{1}&:>&S_{2}\\Q_{1}\cdot q\cdot Q_{2}&:>&Q_{1}\cdot W\cdot Q_{2}\\\end{array}}$

In this usage, the characterization $S_{1}:>S_{2}$ is tantamount to a grammatical license to transform a string of the form $Q_{1}\cdot q\cdot Q_{2}$ into a string of the form $Q1\cdot W\cdot Q2,$ in effect, replacing the non-terminal symbol $q$ with the non-initial string $W$ in any selected, preserved, and closely adjoining context of the form $Q1\cdot {\underline {~~~}}\cdot Q2.$ In this application the notation $S_{1}:>S_{2}$ can be read to say that $S_{1}$ produces $S_{2}$ or that $S_{1}$ transforms into $S_{2}.$

An immediate derivation in ${\mathfrak {G}}$ is an ordered pair $(W,W^{\prime })$ of sentential forms in ${\mathfrak {G}}$ such that:

${\begin{array}{llll}W=Q_{1}\cdot X\cdot Q_{2},&W'=Q_{1}\cdot Y\cdot Q_{2},&{\text{and}}&(X,Y)\in {\mathfrak {K}}.\end{array}}$

As noted above, it is usual to express the condition $(X,Y)\in {\mathfrak {K}}$ by writing $X:>Y\,{\text{in}}\,{\mathfrak {G}}.$

The immediate derivation relation is indicated by saying that $W$ immediately derives $W',$ by saying that $W'$ is immediately derived from $W$ in ${\mathfrak {G}},$ and also by writing:

$W::>W'.$

A derivation in ${\mathfrak {G}}$ is a finite sequence $(W_{1},\ldots ,W_{k})$ of sentential forms over ${\mathfrak {G}}$ such that each adjacent pair $(W_{j},W_{j+1})$ of sentential forms in the sequence is an immediate derivation in ${\mathfrak {G}},$ in other words, such that:

$W_{j}::>W_{j+1},\ {\text{for all}}\ j=1\ {\text{to}}\ k-1.$

If there exists a derivation $(W_{1},\ldots ,W_{k})$ in ${\mathfrak {G}},$ one says that $W_{1}$ derives $W_{k}$ in ${\mathfrak {G}}$ or that $W_{k}$ is derivable from $W_{1}$ in ${\mathfrak {G}},$ and one typically summarizes the derivation by writing:

$W_{1}:\!*\!:>W_{k}.$

The language ${\mathfrak {L}}={\mathfrak {L}}({\mathfrak {G}})=\langle {\mathfrak {G}}\rangle$ that is generated by the formal grammar ${\mathfrak {G}}=(\,^{\backprime \backprime }S\,^{\prime \prime },\,{\mathfrak {Q}},\,{\mathfrak {A}},\,{\mathfrak {K}}\,)$ is the set of strings over the terminal alphabet ${\mathfrak {A}}$ that are derivable from the initial symbol $^{\backprime \backprime }S\,^{\prime \prime }$ by way of the intermediate symbols in ${\mathfrak {Q}}$ according to the characterizations in ${\mathfrak {K}}.$ In sum:

${\mathfrak {L}}({\mathfrak {G}})\ =\ \langle {\mathfrak {G}}\rangle \ =\ \{\,W\in {\mathfrak {A}}^{*}\,:\,^{\backprime \backprime }S\,^{\prime \prime }\,:\!*\!:>\,W\,\}.$

Finally, a string $W$ is called a word, a sentence, or so on, of the language generated by ${\mathfrak {G}}$ if and only if $W$ is in ${\mathfrak {L}}({\mathfrak {G}}).$

---

• Overview • Part 1 • Part 2 • Part 3 • References • Document History •

---