Inquiry Driven Systems • Part 3

Author: Jon Awbrey

• Overview • Part 1 • Part 2 • Part 3 • Part 4 • Part 5 • Part 6 • Part 7 • Part 8 • Part 9 • Part 10 • Part 11 • Part 12 • Part 13 • Part 14 • Part 15 • Part 16 • Appendix A1 • Appendix A2 • References • Document History •

Cactus Language • 1

Thus, what looks to us like a sphere of scientific knowledge more accurately should be represented as the inside of a highly irregular and spiky object, like a pincushion or porcupine, with very sharp extensions in certain directions, and virtually no knowledge in immediately adjacent areas. If our intellectual gaze could shift slightly, it would alter each quill's direction, and suddenly our entire reality would change.

— Herbert J. Bernstein, “Idols of Modern Science”, [HJB, 38]

In this and the four subsections that follow, I describe a calculus for representing propositions as sentences, in other words, as syntactically defined sequences of signs, and for manipulating these sentences chiefly in the light of their semantically defined contents, in other words, with respect to their logical values as propositions. In their computational representation, the expressions of this calculus parse into a class of tree-like data structures called painted cacti. This is a family of graph-theoretic data structures that can be observed to have especially nice properties, turning out to be not only useful from a computational standpoint but also quite interesting from a theoretical point of view. The rest of this subsection serves to motivate the development of this calculus and treats a number of general issues that surround the topic.

In order to facilitate the use of propositions as indicator functions it helps to acquire a flexible notation for referring to propositions in that light, for interpreting sentences in a corresponding role, and for negotiating the requirements of mutual sense between the two domains. If none of the formalisms that are readily available or in common use are able to meet all of the design requirements that come to mind, then it is necessary to contemplate the design of a new language that is especially tailored to the purpose. In the present application, there is a pressing need to devise a general calculus for composing propositions, computing their values on particular arguments, and inverting their indications to arrive at the sets of things in the universe that are indicated by them.

For computational purposes, it is convenient to have a middle ground or an intermediate language for negotiating between the koine of sentences regarded as strings of literal characters and the realm of propositions regarded as objects of logical value, even if this renders it necessary to introduce an artificial medium of exchange between these two domains. If one envisions these computations to be carried out in any organized fashion, and ultimately or partially by means of the familiar sorts of machines, then the strings that express these logical propositions are likely to find themselves parsed into tree-like data structures at some stage of the game. With regard to their abstract structures as graphs, there are several species of graph-theoretic data structures that can be used to accomplish this job in a reasonably effective and efficient way.

Over the course of this project, I plan to use two species of graphs:

Painted And Rooted Cacti (PARCAI).
Painted And Rooted Conifers (PARCOI).

For now, it is enough to discuss the former class of data structures, leaving the consideration of the latter class to a part of the project where their distinctive features are key to developments at that stage. Accordingly, within the context of the current patch of discussion, or until it becomes necessary to attach further notice to the conceivable varieties of parse graphs, the acronym "PARC" is sufficient to indicate the pertinent genus of abstract graphs that are under consideration.

By way of making these tasks feasible to carry out on a regular basis, a prospective language designer is required not only to supply a fluent medium for the expression of propositions, but further to accompany the assertions of their sentences with a canonical mechanism for teasing out the fibers of their indicator functions. Accordingly, with regard to a body of conceivable propositions, one needs to furnish a standard array of techniques for following the threads of their indications from their objective universe to their values for the mind and back again, that is, for tracing the clues that sentences provide from the universe of their objects to the signs of their values, and, in turn, from signs to objects. Ultimately, one seeks to render propositions so functional as indicators of sets and so essential for examining the equality of sets that they can constitute a veritable criterion for the practical conceivability of sets. Tackling this task requires me to introduce a number of new definitions and a collection of additional notational devices, to which I now turn.

Depending on whether a formal language is called by the type of sign that makes it up or whether it is named after the type of object that its signs are intended to denote, one may refer to this cactus language as a sentential calculus or as a propositional calculus, respectively.

When the syntactic definition of the language is well enough understood, then the language can begin to acquire a semantic function. In natural circumstances, the syntax and the semantics are likely to be engaged in a process of co-evolution, whether in ontogeny or in phylogeny, that is, the two developments probably form parallel sides of a single bootstrap. But this is not always the easiest way, at least, at first, to formally comprehend the nature of their action or the power of their interaction.

According to the customary mode of formal reconstruction, the language is first presented in terms of its syntax, in other words, as a formal language of strings called sentences, amounting to a particular subset of the possible strings that can be formed on a finite alphabet of signs. A syntactic definition of the cactus language, one that proceeds along purely formal lines, is carried out in the next Subsection. After that, the development of the language's more concrete aspects can be seen as a matter of defining two functions:

The first is a function that takes each sentence of the language into a computational data structure, to be exact, a tree-like parse graph called a painted cactus.
The second is a function that takes each sentence of the language, or its interpolated parse graph, into a logical proposition, in effect, ending up with an indicator function as the object denoted by the sentence.

The discussion of syntax brings up a number of associated issues that have to be clarified before going on. These are questions of style, that is, the sort of description, grammar, or theory that one finds available or chooses as preferable for a given language. These issues are discussed in the Subsection after next (Subsection 1.3.10.10).

There is an aspect of syntax that is so schematic in its basic character that it can be conveyed by computational data structures, so algorithmic in its uses that it can be automated by routine mechanisms, and so fixed in its nature that its practical exploitation can be served by the usual devices of computation. Because it involves the transformation of signs, it can be recognized as an aspect of semiotics. Since it can be carried out in abstraction from meaning, it is not up to the level of semantics, much less a complete pragmatics, though it does incline to the pragmatic aspects of computation that are auxiliary to and incidental to the human use of language. Therefore, I refer to this aspect of formal language use as the algorithmics or the mechanics of language processing. A mechanical conversion of the cactus language into its associated data structures is discussed in Subsection 1.3.10.11.

In the usual way of proceeding on formal grounds, meaning is added by giving each grammatical sentence, or each syntactically distinguished string, an interpretation as a logically meaningful sentence, in effect, equipping or providing each abstractly well-formed sentence with a logical proposition for it to denote. A semantic interpretation of the cactus language is carried out in Subsection 1.3.10.12.

Syntax

Picture two different configurations of such an irregular shape, superimposed on each other in space, like a double exposure photograph. Of the two images, the only part which coincides is the body. The two different sets of quills stick out into very different regions of space. The objective reality we see from within the first position, seemingly so full and spherical, actually agrees with the shifted reality only in the body of common knowledge. In every direction in which we look at all deeply, the realm of discovered scientific truth could be quite different. Yet in each of those two different situations, we would have thought the world complete, firmly known, and rather round in its penetration of the space of possible knowledge.

— Herbert J. Bernstein, "Idols of Modern Science", [HJB, 38]

In this Subsection, I describe the syntax of a family of formal languages that I intend to use as a sentential calculus, and thus to interpret for the purpose of reasoning about propositions and their logical relations. In order to carry out the discussion, I need a way of referring to signs as if they were objects like any others, in other words, as the sorts of things that are subject to being named, indicated, described, discussed, and renamed if necessary, that can be placed, arranged, and rearranged within a suitable medium of expression, or else manipulated in the mind, that can be articulated and decomposed into their elementary signs, and that can be strung together in sequences to form complex signs. Signs that have signs as their objects are called higher order signs, and this is a topic that demands an apt formalization, but in due time. The present discussion requires a quicker way to get into this subject, even if it takes informal means that cannot be made absolutely precise.

As a temporary notation, let the relationship between a particular sign $s$ and a particular object $o$ , namely, the fact that $s$ denotes $o$ or the fact that $o$ is denoted by $s$ , be symbolized in one of the following two ways:

${\begin{array}{lccc}1.&s&\rightarrow &o\\\\2.&o&\leftarrow &s\\\end{array}}$

Now consider the following paradigm:

${\begin{array}{llccc}1.&\mathrm {If} &{}^{\backprime \backprime }\mathrm {A} {}^{\prime \prime }&\rightarrow &\mathrm {Ann} ,\\&\mathrm {that~is} ,&{}^{\backprime \backprime }\mathrm {A} {}^{\prime \prime }&\mathrm {denotes} &\mathrm {Ann} ,\\&\mathrm {then} &\mathrm {A} &=&\mathrm {Ann} \\&\mathrm {and} &\mathrm {Ann} &=&\mathrm {A} .\\&\mathrm {Thus} &{}^{\backprime \backprime }\mathrm {Ann} {}^{\prime \prime }&\rightarrow &\mathrm {A} ,\\&\mathrm {that~is} ,&{}^{\backprime \backprime }\mathrm {Ann} {}^{\prime \prime }&\mathrm {denotes} &\mathrm {A} .\\\end{array}}$

${\begin{array}{llccc}2.&\mathrm {If} &\mathrm {Bob} &\leftarrow &{}^{\backprime \backprime }\mathrm {B} {}^{\prime \prime },\\&\mathrm {that~is} ,&\mathrm {Bob} &\mathrm {is~denoted~by} &{}^{\backprime \backprime }\mathrm {B} {}^{\prime \prime },\\&\mathrm {then} &\mathrm {Bob} &=&\mathrm {B} \\&\mathrm {and} &\mathrm {B} &=&\mathrm {Bob} .\\&\mathrm {Thus} &\mathrm {B} &\leftarrow &{}^{\backprime \backprime }\mathrm {Bob} {}^{\prime \prime },\\&\mathrm {that~is} ,&\mathrm {B} &\mathrm {is~denoted~by} &{}^{\backprime \backprime }\mathrm {Bob} {}^{\prime \prime }.\\\end{array}}$

When I say that the sign "blank" denotes the sign " ", it means that the string of characters inside the first pair of quotation marks can be used as another name for the string of characters inside the second pair of quotes. In other words, "blank" is a higher order sign whose object is " ", and the string of five characters inside the first pair of quotation marks is a sign at a higher level of signification than the string of one character inside the second pair of quotation marks. This relationship can be abbreviated in either one of the following ways:

${\begin{array}{lll}{}^{\backprime \backprime }\mathrm {~} {}^{\prime \prime }&\leftarrow &{}^{\backprime \backprime }\mathrm {blank} {}^{\prime \prime }\\\\{}^{\backprime \backprime }\mathrm {blank} {}^{\prime \prime }&\rightarrow &{}^{\backprime \backprime }\mathrm {~} {}^{\prime \prime }\\\end{array}}$

Using the raised dot " $\cdot$ " as a sign to mark the articulation of a quoted string into a sequence of possibly shorter quoted strings, and thus to mark the concatenation of a sequence of quoted strings into a possibly larger quoted string, one can write:

${\begin{array}{lllll}{}^{\backprime \backprime }\mathrm {~} {}^{\prime \prime }&\leftarrow &{}^{\backprime \backprime }\mathrm {blank} {}^{\prime \prime }&=&{}^{\backprime \backprime }\mathrm {b} {}^{\prime \prime }\,\cdot \,{}^{\backprime \backprime }\mathrm {l} {}^{\prime \prime }\,\cdot \,{}^{\backprime \backprime }\mathrm {a} {}^{\prime \prime }\,\cdot \,{}^{\backprime \backprime }\mathrm {n} {}^{\prime \prime }\,\cdot \,{}^{\backprime \backprime }\mathrm {k} {}^{\prime \prime }\\\end{array}}$

This usage allows us to refer to the blank as a type of character, and also to refer any blank we choose as a token of this type, referring to either of them in a marked way, but without the use of quotation marks, as I just did. Now, since a blank is just what the name "blank" names, it is possible to represent the denotation of the sign " " by the name "blank" in the form of an identity between the named objects, thus:

${\begin{array}{lll}{}^{\backprime \backprime }\mathrm {~} {}^{\prime \prime }&=&\mathrm {blank} \\\end{array}}$

With these kinds of identity in mind, it is possible to extend the use of the " $\cdot$ " sign to mark the articulation of either named or quoted strings into both named and quoted strings. For example:

${\begin{array}{lclcl}{}^{\backprime \backprime }\mathrm {~~} {}^{\prime \prime }&=&{}^{\backprime \backprime }\mathrm {~} {}^{\prime \prime }\,\cdot \,{}^{\backprime \backprime }\mathrm {~} {}^{\prime \prime }&=&\mathrm {blank} \,\cdot \,\mathrm {blank} \\\\{}^{\backprime \backprime }\mathrm {~blank} {}^{\prime \prime }&=&{}^{\backprime \backprime }\mathrm {~} {}^{\prime \prime }\,\cdot \,{}^{\backprime \backprime }\mathrm {blank} {}^{\prime \prime }&=&\mathrm {blank} \,\cdot \,{}^{\backprime \backprime }\mathrm {blank} {}^{\prime \prime }\\\\{}^{\backprime \backprime }\mathrm {blank~} {}^{\prime \prime }&=&{}^{\backprime \backprime }\mathrm {blank} {}^{\prime \prime }\,\cdot \,{}^{\backprime \backprime }\mathrm {~} {}^{\prime \prime }&=&{}^{\backprime \backprime }\mathrm {blank} {}^{\prime \prime }\,\cdot \,\mathrm {blank} \end{array}}$

A few definitions from formal language theory are required at this point.

An alphabet is a finite set of signs, typically, ${\mathfrak {A}}=\{{\mathfrak {a}}_{1},\ldots ,{\mathfrak {a}}_{n}\}.$

A string over an alphabet ${\mathfrak {A}}$ is a finite sequence of signs from ${\mathfrak {A}}.$

The length of a string is just its length as a sequence of signs.

The empty string is the unique sequence of length 0. It is sometimes denoted by an empty pair of quotation marks, $^{\backprime \backprime \prime \prime },$ but more often by the Greek symbols epsilon or lambda.

A sequence of length $k>0$ is typically presented in the concatenated forms:

$s_{1}s_{2}\ldots s_{k-1}s_{k}$

or

$s_{1}\cdot s_{2}\cdot \ldots \cdot s_{k-1}\cdot s_{k}$

with $s_{j}\in {\mathfrak {A}}$ for all $j=1\ldots k.$

Two alternative notations are often useful:

$\varepsilon$	=	${}^{\backprime \backprime \prime \prime }$	=	the empty string.
${\underline {\varepsilon }}$	=	$\{\varepsilon \}$	=	the language consisting of a single empty string.

The kleene star ${\mathfrak {A}}^{*}$ of alphabet ${\mathfrak {A}}$ is the set of all strings over ${\mathfrak {A}}.$ In particular, ${\mathfrak {A}}^{*}$ includes among its elements the empty string $\varepsilon .$

The kleene plus ${\mathfrak {A}}^{+}$ of an alphabet ${\mathfrak {A}}$ is the set of all positive length strings over ${\mathfrak {A}},$ in other words, everything in ${\mathfrak {A}}^{*}$ but the empty string.

A formal language ${\mathfrak {L}}$ over an alphabet ${\mathfrak {A}}$ is a subset of ${\mathfrak {A}}^{*}.$ In brief, ${\mathfrak {L}}\subseteq {\mathfrak {A}}^{*}.$ If $s$ is a string over ${\mathfrak {A}}$ and if $s$ is an element of ${\mathfrak {L}},$ then it is customary to call $s$ a sentence of ${\mathfrak {L}}.$ Thus, a formal language ${\mathfrak {L}}$ is defined by specifying its elements, which amounts to saying what it means to be a sentence of ${\mathfrak {L}}.$

One last device turns out to be useful in this connection. If $s$ is a string that ends with a sign $t,$ then $s\cdot t^{-1}$ is the string that results by deleting from $s$ the terminal $t.$

In this context, I make the following distinction:

To delete an appearance of a sign is to replace it with an appearance of the empty string "".
To erase an appearance of a sign is to replace it with an appearance of the blank symbol " ".

A token is a particular appearance of a sign.

The informal mechanisms that have been illustrated in the immediately preceding discussion are enough to equip the rest of this discussion with a moderately exact description of the so-called cactus language that I intend to use in both my conceptual and my computational representations of the minimal formal logical system that is variously known to sundry communities of interpretation as propositional logic, sentential calculus, or more inclusively, zeroth order logic (ZOL).

The painted cactus language ${\mathfrak {C}}$ is actually a parameterized family of languages, consisting of one language ${\mathfrak {C}}({\mathfrak {P}})$ for each set ${\mathfrak {P}}$ of paints.

The alphabet ${\mathfrak {A}}={\mathfrak {M}}\cup {\mathfrak {P}}$ is the disjoint union of two sets of symbols:

${\mathfrak {M}}$ is the alphabet of measures, the set of punctuation marks, or the collection of syntactic constants that is common to all of the languages ${\mathfrak {C}}({\mathfrak {P}}).$ This set of signs is given as follows:

${\begin{array}{lccccccccccc}{\mathfrak {M}}&=&\{&{\mathfrak {m}}_{1}&,&{\mathfrak {m}}_{2}&,&{\mathfrak {m}}_{3}&,&{\mathfrak {m}}_{4}&\}\\&=&\{&{}^{\backprime \backprime }\,\mathrm {~} \,{}^{\prime \prime }&,&{}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }&,&{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }&,&{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }&\}\\&=&\{&\mathrm {blank} &,&\mathrm {links} &,&\mathrm {comma} &,&\mathrm {right} &\}\\\end{array}}$
${\mathfrak {P}}$ is the palette, the alphabet of paints, or the collection of syntactic variables that is peculiar to the language ${\mathfrak {C}}({\mathfrak {P}}).$ This set of signs is given as follows:

${\mathfrak {P}}=\{{\mathfrak {p}}_{j}:j\in J\}.$

The easiest way to define the language ${\mathfrak {C}}({\mathfrak {P}})$ is to indicate the general sorts of operations that suffice to construct the greater share of its sentences from the specified few of its sentences that require a special election. In accord with this manner of proceeding, I introduce a family of operations on strings of ${\mathfrak {A}}^{*}$ that are called syntactic connectives. If the strings on which they operate are exclusively sentences of ${\mathfrak {C}}({\mathfrak {P}}),$ then these operations are tantamount to sentential connectives, and if the syntactic sentences, considered as abstract strings of meaningless signs, are given a semantics in which they denote propositions, considered as indicator functions over some universe, then these operations amount to propositional connectives.

Rather than presenting the most concise description of these languages right from the beginning, it serves comprehension to develop a picture of their forms in gradual stages, starting from the most natural ways of viewing their elements, if somewhat at a distance, and working through the most easily grasped impressions of their structures, if not always the sharpest acquaintances with their details.

The first step is to define two sets of basic operations on strings of ${\mathfrak {A}}^{*}.$

The concatenation of one string $s_{1}$ is just the string $s_{1}.$

The concatenation of two strings ${s_{1},s_{2}}$ is the string ${s_{1}\cdot s_{2}}.$

The concatenation of the $k$ strings ${(s_{j})_{j=1}^{k}}$ is the string of the form ${s_{1}\cdot \ldots \cdot s_{k}}.$
The surcatenation of one string $s_{1}$ is the string ${}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,s_{1}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$

The surcatenation of two strings ${s_{1},s_{2}}$ is ${}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,s_{1}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,s_{2}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$

The surcatenation of the $k$ strings ${(s_{j})_{j=1}^{k}}$ is the string of the form ${}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,s_{1}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,\ldots \,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,s_{k}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$

These definitions can be made a little more succinct by defining the following sorts of generic operators on strings:

The concatenation $\mathrm {Conc} _{j=1}^{k}$ of the sequence of $k$ strings $(s_{j})_{j=1}^{k}$ is defined recursively as follows:

$\mathrm {Conc} _{j=1}^{1}s_{j}\ =\ s_{1}.$
For $\ell >1,$

$\mathrm {Conc} _{j=1}^{\ell }s_{j}\ =\ \mathrm {Conc} _{j=1}^{\ell -1}s_{j}\,\cdot \,s_{\ell }.$

The surcatenation $\mathrm {Surc} _{j=1}^{k}$ of the sequence of $k$ strings $(s_{j})_{j=1}^{k}$ is defined recursively as follows:

$\mathrm {Surc} _{j=1}^{1}s_{j}\ =\ {}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,s_{1}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$
For $\ell >1,$

$\mathrm {Surc} _{j=1}^{\ell }s_{j}\ =\ \mathrm {Surc} _{j=1}^{\ell -1}s_{j}\,\cdot \,(\,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\,)^{-1}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,s_{\ell }\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$

The definitions of these syntactic operations can now be organized in a slightly better fashion by making a few additional conventions and auxiliary definitions.

The conception of the $k$ -place concatenation operation can be extended to include its natural prequel:

$\mathrm {Conc} ^{0}\ =\ ^{\backprime \backprime \prime \prime }$ = the empty string.

Next, the construction of the $k$ -place concatenation can be broken into stages by means of the following conceptions:

The precatenation $\mathrm {Prec} (s_{1},s_{2})$ of the two strings $s_{1},s_{2}$ is the string that is defined as follows:

$\mathrm {Prec} (s_{1},s_{2})\ =\ s_{1}\cdot s_{2}.$
The concatenation of the sequence of $k$ strings $s_{1},\ldots ,s_{k}$ can now be defined as an iterated precatenation over the sequence of $k+1$ strings that begins with the string $s_{0}=\mathrm {Conc} ^{0}\,=\,^{\backprime \backprime \prime \prime }$ and then continues on through the other $k$ strings:

$\mathrm {Conc} _{j=0}^{0}s_{j}\ =\ \mathrm {Conc} ^{0}\ =\ ^{\backprime \backprime \prime \prime }.$
For $\ell >0,$

$\mathrm {Conc} _{j=1}^{\ell }s_{j}\ =\ \mathrm {Prec} (\mathrm {Conc} _{j=0}^{\ell -1}s_{j},s_{\ell }).$

The conception of the $k$ -place surcatenation operation can be extended to include its natural "prequel":

$\mathrm {Surc} ^{0}\ =\ {}^{\backprime \backprime }\,\mathrm {()} \,{}^{\prime \prime }.$

Finally, the construction of the $k$ -place surcatenation can be broken into stages by means of the following conceptions:
1. A subclause in ${\mathfrak {A}}^{*}$ is a string that ends with a ${}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$
2. The subcatenation $\mathrm {Subc} (s_{1},s_{2})$ of a subclause $s_{1}$ by a string $s_{2}$ is the string that is defined as follows:
  
  $\mathrm {Subc} (s_{1},s_{2})\ =\ s_{1}\,\cdot \,(\,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\,)^{-1}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,s_{2}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$
3. The surcatenation of the $k$ strings $s_{1},\ldots ,s_{k}$ can now be defined as an iterated subcatenation over the sequence of $k+1$ strings that starts with the string $s_{0}\ =\ \mathrm {Surc} ^{0}\ =\ {}^{\backprime \backprime }\,\mathrm {()} \,{}^{\prime \prime }$ and then continues on through the other $k$ strings:

Notice that the expressions $\mathrm {Conc} _{j=0}^{0}s_{j}$ and $\mathrm {Surc} _{j=0}^{0}s_{j}$ are defined in such a way that the respective operators $\mathrm {Conc} ^{0}$ and $\mathrm {Surc} ^{0}$ simply ignore, in the manner of constants, whatever sequences of strings $s_{j}$ may be listed as their ostensible arguments.

Having defined the basic operations of concatenation and surcatenation on arbitrary strings, in effect, giving them operational meaning for the all-inclusive language ${\mathfrak {L}}={\mathfrak {A}}^{*},$ it is time to adjoin the notion of a more discriminating grammaticality, in other words, a more properly restrictive concept of a sentence.

If ${\mathfrak {L}}$ is an arbitrary formal language over an alphabet of the sort that we are talking about, that is, an alphabet of the form ${\mathfrak {A}}={\mathfrak {M}}\cup {\mathfrak {P}},$ then there are a number of basic structural relations that can be defined on the strings of ${\mathfrak {L}}.$

1.	$s$ is the concatenation of $s_{1}$ and $s_{2}$ in ${\mathfrak {L}}$ if and only if
	$s_{1}$ is a sentence of ${\mathfrak {L}},$ $s_{2}$ is a sentence of ${\mathfrak {L}},$ and
	$s=s_{1}\cdot s_{2}.$
2.	$s$ is the concatenation of the $k$ strings $s_{1},\ldots ,s_{k}$ in ${\mathfrak {L}},$
	if and only if $s_{j}$ is a sentence of ${\mathfrak {L}},$ for all $j=1\ldots k,$ and
	$s=\mathrm {Conc} _{j=1}^{k}s_{j}=s_{1}\cdot \ldots \cdot s_{k}.$
3.	$s$ is the discatenation of $s_{1}$ by $t$ if and only if
	$s_{1}$ is a sentence of ${\mathfrak {L}},$ $t$ is an element of ${\mathfrak {A}},$ and
	$s_{1}=s\cdot t.$
	When this is the case, one more commonly writes:
	$s=s_{1}\cdot t^{-1}.$
4.	$s$ is a subclause of ${\mathfrak {L}}$ if and only if
	$s$ is a sentence of ${\mathfrak {L}}$ and $s$ ends with a ${}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$
5.	$s$ is the subcatenation of $s_{1}$ by $s_{2}$ if and only if
	$s_{1}$ is a subclause of ${\mathfrak {L}},$ $s_{2}$ is a sentence of ${\mathfrak {L}},$ and
	$s=s_{1}\,\cdot \,(\,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\,)^{-1}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,s_{2}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$
6.	$s$ is the surcatenation of the $k$ strings $s_{1},\ldots ,s_{k}$ in ${\mathfrak {L}},$
	if and only if $s_{j}$ is a sentence of ${\mathfrak {L}},$ for all ${j=1\ldots k},$ and
	$s\ =\ \mathrm {Surc} _{j=1}^{k}s_{j}\ =\ {}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,s_{1}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,\ldots \,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,s_{k}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$

The converses of these decomposition relations are tantamount to the corresponding forms of composition operations, making it possible for these complementary forms of analysis and synthesis to articulate the structures of strings and sentences in two directions.

The painted cactus language with paints in the set ${\mathfrak {P}}=\{p_{j}:j\in J\}$ is the formal language ${\mathfrak {L}}={\mathfrak {C}}({\mathfrak {P}})\subseteq {\mathfrak {A}}^{*}=({\mathfrak {M}}\cup {\mathfrak {P}})^{*}$ that is defined as follows:

PC 1.	The blank symbol $m_{1}$ is a sentence.
PC 2.	The paint $p_{j}$ is a sentence, for each $j$ in $J.$
PC 3.	$\mathrm {Conc} ^{0}$ and $\mathrm {Surc} ^{0}$ are sentences.
PC 4.	For each positive integer $k,$
	if $s_{1},\ldots ,s_{k}$ are sentences,
	then $\mathrm {Conc} _{j=1}^{k}s_{j}$ is a sentence,
	and $\mathrm {Surc} _{j=1}^{k}s_{j}$ is a sentence.

As usual, saying that $s$ is a sentence is just a conventional way of stating that the string $s$ belongs to the relevant formal language ${\mathfrak {L}}.$ An individual sentence of ${\mathfrak {C}}({\mathfrak {P}}),$ for any palette ${\mathfrak {P}},$ is referred to as a painted and rooted cactus expression (PARCE) on the palette ${\mathfrak {P}},$ or a cactus expression, for short. Anticipating the forms that the parse graphs of these PARCE's will take, to be described in the next Subsection, the language ${\mathfrak {L}}={\mathfrak {C}}({\mathfrak {P}})$ is also described as the set $\mathrm {PARCE} ({\mathfrak {P}})$ of PARCE's on the palette ${\mathfrak {P}},$ more generically, as the PARCE's that constitute the language $\mathrm {PARCE} .$

A bare PARCE, a bit loosely referred to as a bare cactus expression, is a PARCE on the empty palette ${\mathfrak {P}}=\varnothing .$ A bare PARCE is a sentence in the bare cactus language, ${\mathfrak {C}}^{0}={\mathfrak {C}}(\varnothing )=\mathrm {PARCE} ^{0}=\mathrm {PARCE} (\varnothing ).$ This set of strings, regarded as a formal language in its own right, is a sublanguage of every cactus language ${\mathfrak {C}}({\mathfrak {P}}).$ A bare cactus expression is commonly encountered in practice when one has occasion to start with an arbitrary PARCE and then finds a reason to delete or to erase all of its paints.

Only one thing remains to cast this description of the cactus language into a form that is commonly found acceptable. As presently formulated, the principle PC 4 appears to be attempting to define an infinite number of new concepts all in a single step, at least, it appears to invoke the indefinitely long sequences of operators, $\mathrm {Conc} ^{k}$ and $\mathrm {Surc} ^{k},$ for all $k>0.$ As a general rule, one prefers to have an effectively finite description of conceptual objects, and this means restricting the description to a finite number of schematic principles, each of which involves a finite number of schematic effects, that is, a finite number of schemata that explicitly relate conditions to results.

A start in this direction, taking steps toward an effective description of the cactus language, a finitary conception of its membership conditions, and a bounded characterization of a typical sentence in the language, can be made by recasting the present description of these expressions into the pattern of what is called, more or less roughly, a formal grammar.

A notation in the style of $S:>T$ is now introduced, to be read among many others in this manifold of ways:

S\ \mathrm {covers} \ T

S\ \mathrm {governs} \ T

S\ \mathrm {rules} \ T

S\ \mathrm {subsumes} \ T

S\ \mathrm {types~over} \ T

The form $S:>T$ is here recruited for polymorphic employment in at least the following types of roles:

To signify that an individually named or quoted string $T$ is being typed as a sentence $S$ of the language of interest ${\mathfrak {L}}.$
To express the fact or to make the assertion that each member of a specified set of strings $T\subseteq {\mathfrak {A}}^{*}$ also belongs to the syntactic category $S,$ the one that qualifies a string as being a sentence in the relevant formal language ${\mathfrak {L}}.$
To specify the intension or to signify the intention that every string that fits the conditions of the abstract type $T$ must also fall under the grammatical heading of a sentence, as indicated by the type $S,$ all within the target language ${\mathfrak {L}}.$

In these types of situation the letter ${}^{\backprime \backprime }S\,{}^{\prime \prime }$ that signifies the type of a sentence in the language of interest, is called the initial symbol or the sentence symbol of a candidate formal grammar for the language, while any number of letters like ${}^{\backprime \backprime }T\,{}^{\prime \prime }$ signifying other types of strings that are necessary to a reasonable account or a rational reconstruction of the sentences that belong to the language, are collectively referred to as intermediate symbols.

Combining the singleton set $\{{}^{\backprime \backprime }S\,{}^{\prime \prime }\}$ whose sole member is the initial symbol with the set ${\mathfrak {Q}}$ that assembles together all of the intermediate symbols results in the set $\{{}^{\backprime \backprime }S\,{}^{\prime \prime }\}\cup {\mathfrak {Q}}$ of non-terminal symbols. Completing the package, the alphabet ${\mathfrak {A}}$ of the language is also known as the set of terminal symbols. In this discussion, I will adopt the convention that ${\mathfrak {Q}}$ is the set of intermediate symbols, but I will often use $q$ as a typical variable that ranges over all of the non-terminal symbols, $q\in \{{}^{\backprime \backprime }S\,{}^{\prime \prime }\}\cup {\mathfrak {Q}}.$ Finally, it is convenient to refer to all of the symbols in $\{{}^{\backprime \backprime }S\,{}^{\prime \prime }\}\cup {\mathfrak {Q}}\cup {\mathfrak {A}}$ as the augmented alphabet of the prospective grammar for the language, and accordingly to describe the strings in $(\{{}^{\backprime \backprime }S\,{}^{\prime \prime }\}\cup {\mathfrak {Q}}\cup {\mathfrak {A}})^{*}$ as the augmented strings, in effect, expressing the forms that are superimposed on a language by one of its conceivable grammars. In certain settings it becomes desirable to separate the augmented strings that contain the symbol ${}^{\backprime \backprime }S\,{}^{\prime \prime }$ from all other sorts of augmented strings. In these situations the strings in the disjoint union $\{{}^{\backprime \backprime }S\,{}^{\prime \prime }\}\cup ({\mathfrak {Q}}\cup {\mathfrak {A}})^{*}$ are known as the sentential forms of the associated grammar.

In forming a grammar for a language statements of the form $W:>W',$ where $W$ and $W'$ are augmented strings or sentential forms of specified types that depend on the style of the grammar that is being sought, are variously known as characterizations, covering rules, productions, rewrite rules, subsumptions, transformations, or typing rules. These are collected together into a set ${\mathfrak {K}}$ that serves to complete the definition of the formal grammar in question.

Correlative with the use of this notation, an expression of the form $T<:S,$ read to say that $T$ is covered by $S,$ can be interpreted to say that $T$ is of the type $S.$ Depending on the context, this can be taken in either one of two ways:

Treating $T$ as a string variable, it means that the individual string $T$ is typed as $S.$
Treating $T$ as a type name, it means that any instance of the type $T$ also falls under the type $S.$

In accordance with these interpretations, an expression of the form $t<:T$ can be read in all of the ways that one typically reads an expression of the form $t:T.$

There are several abuses of notation that commonly tolerated in the use of covering relations. The worst offense is that of allowing symbols to stand equivocally either for individual strings or else for their types. There is a measure of consistency to this practice, considering the fact that perfectly individual entities are rarely if ever grasped by means of signs and finite expressions, which entails that every appearance of an apparent token is only a type of more particular tokens, and meaning in the end that there is never any recourse but to the sort of discerning interpretation that can decide just how each sign is intended. In view of all this, I continue to permit expressions like $t<:T$ and $T<:S,$ where any of the symbols $t,T,S$ can be taken to signify either the tokens or the subtypes of their covering types.

Note. For some time to come in the discussion that follows, although I will continue to focus on the cactus language as my principal object example, my more general purpose will be to develop the subject matter of the formal languages and grammars. I will do this by taking up a particular method of stepwise refinement and using it to extract a rigorous formal grammar for the cactus language, starting with little more than a rough description of the target language and applying a systematic analysis to develop a sequence of increasingly more effective and more exact approximations to the desired grammar.

Employing the notion of a covering relation it becomes possible to redescribe the cactus language ${\mathfrak {L}}={\mathfrak {C}}({\mathfrak {P}})$ in the following ways.

Grammar 1

Grammar 1 is something of a misnomer. It is nowhere near exemplifying any kind of a standard form and it is only intended as a starting point for the initiation of more respectable grammars. Such as it is, it uses the terminal alphabet ${\mathfrak {A}}={\mathfrak {M}}\cup {\mathfrak {P}}$ that comes with the territory of the cactus language ${\mathfrak {C}}({\mathfrak {P}}),$ it specifies ${\mathfrak {Q}}=\varnothing ,$ in other words, it employs no intermediate symbols, and it embodies the covering set ${\mathfrak {K}}$ as listed in the following display.

${\mathfrak {C}}({\mathfrak {P}}):{\text{Grammar 1}}$

${\mathfrak {Q}}=\varnothing$

${\begin{array}{rcll}1.&S&:>&m_{1}\ =\ {}^{\backprime \backprime }\mathrm {~} {}^{\prime \prime }\\2.&S&:>&p_{j},\,{\text{for each}}\,j\in J\\3.&S&:>&\mathrm {Conc} ^{0}\ =\ ^{\backprime \backprime \prime \prime }\\4.&S&:>&\mathrm {Surc} ^{0}\ =\ {}^{\backprime \backprime }\,\mathrm {()} \,{}^{\prime \prime }\\5.&S&:>&S^{*}\\6.&S&:>&{}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,S\,\cdot \,(\,{}^{\backprime \backprime }\mathrm {,} {}^{\prime \prime }\,\cdot \,S\,)^{*}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\\\end{array}}$

In this formulation, the last two lines specify that:

The concept of a sentence in ${\mathfrak {L}}$ covers any concatenation of sentences in ${\mathfrak {L}},$ in effect, any number of freely chosen sentences that are available to be concatenated one after another.
The concept of a sentence in ${\mathfrak {L}}$ covers any surcatenation of sentences in ${\mathfrak {L}},$ in effect, any string that opens with a ${}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime },$ continues with a sentence, possibly empty, follows with a finite number of phrases of the form ${}^{\backprime \backprime }\mathrm {,} {}^{\prime \prime }\,\cdot \,S,$ and closes with a ${}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }.$

This appears to be just about the most concise description of the cactus language ${\mathfrak {C}}({\mathfrak {P}})$ that one can imagine, but there are a couple of problems that are commonly felt to afflict this style of presentation and to make it less than completely acceptable. Briefly stated, these problems turn on the following properties of the presentation:

The invocation of the kleene star operation is not reduced to a manifestly finitary form.
The type $S$ that indicates a sentence is allowed to cover not only itself but also the empty string.

I will discuss these issues at first in general, and especially in regard to how the two features interact with one another, and then I return to address in further detail the questions that they engender on their individual bases.

In the process of developing a grammar for a language, it is possible to notice a number of organizational, pragmatic, and stylistic questions, whose moment to moment answers appear to decide the ongoing direction of the grammar that develops and the impact of whose considerations work in tandem to determine, or at least to influence, the sort of grammar that turns out. The issues that I can see arising at this point I can give the following prospective names, putting off the discussion of their natures and the treatment of their details to the points in the development of the present example where they evolve their full import.

The degree of intermediate organization in a grammar.
The distinction between empty and significant strings, and thus the distinction between empty and significant types of strings.
The principle of intermediate significance. This is a constraint on the grammar that arises from considering the interaction of the first two issues.

In responding to these issues, it is advisable at first to proceed in a stepwise fashion, all the better to accommodate the chances of pursuing a series of parallel developments in the grammar, to allow for the possibility of reversing many steps in its development, indeed, to take into account the near certain necessity of having to revisit, to revise, and to reverse many decisions about how to proceed toward an optimal description or a satisfactory grammar for the language. Doing all this means exploring the effects of various alterations and innovations as independently from each other as possible.

The degree of intermediate organization in a grammar is measured by how many intermediate symbols it has and by how they interact with each other by means of its productions. With respect to this issue, Grammar 1 has no intermediate symbols at all, ${\mathfrak {Q}}=\varnothing ,$ and therefore remains at an ostensibly trivial degree of intermediate organization. Some additions to the list of intermediate symbols are practically obligatory in order to arrive at any reasonable grammar at all, other inclusions appear to have a more optional character, though obviously useful from the standpoints of clarity and ease of comprehension.

One of the troubles that is perceived to affect Grammar 1 is that it wastes so much of the available potential for efficient description in recounting over and over again the simple fact that the empty string is present in the language. This arises in part from the statement that $S:>S^{*},$ which implies that:

${\begin{array}{lcccccccccccc}S&:>&S^{*}&=&{\underline {\varepsilon }}&\cup &S&\cup &S\cdot S&\cup &S\cdot S\cdot S&\cup &\ldots \\\end{array}}$

There is nothing wrong with the more expansive pan of the covered equation, since it follows straightforwardly from the definition of the kleene star operation, but the covering statement to the effect that $S:>S^{*}$ is not a very productive piece of information, in the sense of telling very much about the language that falls under the type of a sentence $S.$ In particular, since it implies that $S:>{\underline {\varepsilon }},$ and since ${\underline {\varepsilon }}\cdot {\mathfrak {L}}\,=\,{\mathfrak {L}}\cdot {\underline {\varepsilon }}\,=\,{\mathfrak {L}},$ for any formal language ${\mathfrak {L}},$ the empty string $\varepsilon$ is counted over and over in every term of the union, and every non-empty sentence under $S$ appears again and again in every term of the union that follows the initial appearance of $S.$ As a result, this style of characterization has to be classified as true but not very informative. If at all possible, one prefers to partition the language of interest into a disjoint union of subsets, thereby accounting for each sentence under its proper term, and one whose place under the sum serves as a useful parameter of its character or its complexity. In general, this form of description is not always possible to achieve, but it is usually worth the trouble to actualize it whenever it is.

Suppose that one tries to deal with this problem by eliminating each use of the kleene star operation, by reducing it to a purely finitary set of steps, or by finding an alternative way to cover the sublanguage that it is used to generate. This amounts, in effect, to recognizing a type, a complex process that involves the following steps:

Noticing a category of strings that is generated by iteration or recursion.
Acknowledging the fact that it needs to be covered by a non-terminal symbol.
Making a note of it by instituting an explicitly-named grammatical category.

In sum, one introduces a non-terminal symbol for each type of sentence and each part of speech or sentential component that is generated by means of iteration or recursion under the ruling constraints of the grammar. In order to do this one needs to analyze the iteration of each grammatical operation in a way that is analogous to a mathematically inductive definition, but further in a way that is not forced explicitly to recognize a distinct and separate type of expression merely to account for and to recount every increment in the parameter of iteration.

Returning to the case of the cactus language, the process of recognizing an iterative type or a recursive type can be illustrated in the following way. The operative phrases in the simplest sort of recursive definition are its initial part and its generic part. For the cactus language ${\mathfrak {C}}({\mathfrak {P}}),$ one has the following definitions of concatenation as iterated precatenation and of surcatenation as iterated subcatenation, respectively:

${\begin{array}{llll}1.&\mathrm {Conc} _{j=1}^{0}&=&^{\backprime \backprime \prime \prime }\\\\&\mathrm {Conc} _{j=1}^{k}S_{j}&=&\mathrm {Prec} (\mathrm {Conc} _{j=1}^{k-1}S_{j},S_{k})\\\\2.&\mathrm {Surc} _{j=1}^{0}&=&{}^{\backprime \backprime }\,\mathrm {()} \,{}^{\prime \prime }\\\\&\mathrm {Surc} _{j=1}^{k}S_{j}&=&\mathrm {Subc} (\mathrm {Surc} _{j=1}^{k-1}S_{j},S_{k})\\\\\end{array}}$

In order to transform these recursive definitions into grammar rules, one introduces a new pair of intermediate symbols, $\mathrm {Conc}$ and $\mathrm {Surc} ,$ corresponding to the operations that share the same names but ignoring the inflexions of their individual parameters $j$ and $k.$ Recognizing the type of a sentence by means of the initial symbol $S$ and interpreting $\mathrm {Conc}$ and $\mathrm {Surc}$ as names for the types of strings that are generated by concatenation and by surcatenation, respectively, one arrives at the following transformation of the ruling operator definitions into the form of covering grammar rules:

${\begin{array}{llll}1.&\mathrm {Conc} &:>&^{\backprime \backprime \prime \prime }\\\\&\mathrm {Conc} &:>&\mathrm {Conc} \cdot S\\\\2.&\mathrm {Surc} &:>&{}^{\backprime \backprime }\,\mathrm {()} \,{}^{\prime \prime }\\\\&\mathrm {Surc} &:>&{}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,S\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\\\\&\mathrm {Surc} &:>&\mathrm {Surc} \,\cdot \,(\,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\,)^{-1}\,\cdot \,{}^{\backprime \backprime }\mathrm {,} {}^{\prime \prime }\,\cdot \,S\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\end{array}}$

As given, this particular fragment of the intended grammar contains a couple of features that are desirable to amend.

Given the covering $S:>\mathrm {Conc} ,$ the covering rule $\mathrm {Conc} :>\mathrm {Conc} \cdot S$ says no more than the covering rule $\mathrm {Conc} :>S\cdot S.$ Consequently, all of the information contained in these two covering rules is already covered by the statement that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S :> S \cdot S.}
A grammar rule that invokes a notion of decatenation, deletion, erasure, or any other sort of retrograde production, is frequently considered to be lacking in elegance, and a there is a style of critique for grammars that holds it preferable to avoid these types of operations if it is at all possible to do so. Accordingly, contingent on the prescriptions of the informal rule in question, and pursuing the stylistic dictates that are writ in the realm of its aesthetic regime, it becomes necessary for us to backtrack a little bit, to temporarily withdraw the suggestion of employing these elliptical types of operations, but without, of course, eliding the record of doing so.

Grammar 2

One way to analyze the surcatenation of any number of sentences is to introduce an auxiliary type of string, not in general a sentence, but a proper component of any sentence that is formed by surcatenation. Doing this brings one to the following definition:

A tract is a concatenation of a finite sequence of sentences, with a literal comma Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime} \mathrm{,} {}^{\prime\prime}} interpolated between each pair of adjacent sentences. Thus, a typical tract $T$ takes the form:

${\begin{array}{lllllllllll}T&=&S_{1}&\cdot &{}^{\backprime \backprime }\mathrm {,} {}^{\prime \prime }&\cdot &\ldots &\cdot &{}^{\backprime \backprime }\mathrm {,} {}^{\prime \prime }&\cdot &S_{k}\\\end{array}}$

A tract must be distinguished from the abstract sequence of sentences, $S_{1},\ldots ,S_{k},$ where the commas that appear to come to mind, as if being called up to separate the successive sentences of the sequence, remain as partially abstract conceptions, or as signs that retain a disengaged status on the borderline between the text and the mind. In effect, the types of commas that appear to follow in the abstract sequence continue to exist as conceptual abstractions and fail to be cognized in a wholly explicit fashion, whether as concrete tokens in the object language, or as marks in the strings of signs that are able to engage one's parsing attention.

Returning to the case of the painted cactus language ${\mathfrak {L}}={\mathfrak {C}}({\mathfrak {P}}),$ it is possible to put the currently assembled pieces of a grammar together in the light of the presently adopted canons of style, to arrive a more refined analysis of the fact that the concept of a sentence covers any concatenation of sentences and any surcatenation of sentences, and so to obtain the following form of a grammar:

${\mathfrak {C}}({\mathfrak {P}}):{\text{Grammar 2}}$	${\mathfrak {Q}}=\{\,{}^{\backprime \backprime }T\,{}^{\prime \prime }\,\}$
${\begin{array}{rcll}1.&S&:>&\varepsilon \\2.&S&:>&m_{1}\\3.&S&:>&p_{j},\,{\text{for each}}\,j\in J\\4.&S&:>&S\,\cdot \,S\\5.&S&:>&{}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,T\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\\6.&T&:>&S\\7.&T&:>&T\,\cdot \,{}^{\backprime \backprime }\mathrm {,} {}^{\prime \prime }\,\cdot \,S\\\end{array}}$

In this rendition, a string of type $T$ 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 $T$ 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 $T:>S$ means that $T$ inherits all of the initial conditions of $S,$ namely, $T\,:>\,\varepsilon ,m_{1},p_{j}.$ In accord with these simple beginnings it comes to parse that the rule $T\,:>\,T\,\cdot \,{}^{\backprime \backprime }\mathrm {,} {}^{\prime \prime }\,\cdot \,S,$ with the substitutions $T=\varepsilon$ and $S=\varepsilon$ on the covered side of the rule, bears the germinal implication that $T\,:>\,{}^{\backprime \backprime }\mathrm {,} {}^{\prime \prime }.$

Grammar 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 ${\mathfrak {Q}}=\{\,{}^{\backprime \backprime }T\,{}^{\prime \prime }\,\}$ 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

Although it is not strictly necessary to do so, it is possible to organize the materials of our developing grammar in a slightly better fashion by recognizing two recurrent types of strings that appear in the typical cactus expression. In doing this, one arrives at the following two definitions:

A rune is a string of blanks and paints concatenated together. Thus, a typical rune $R$ is a string over $\{m_{1}\}\cup {\mathfrak {P}},$ possibly the empty string:

R\ \in \ (\{m_{1}\}\cup {\mathfrak {P}})^{*}

When there is no possibility of confusion, the letter ${}^{\backprime \backprime }R\,{}^{\prime \prime }$ can be used either as a string variable that ranges over the set of runes or else as a type name for the class of runes. The latter reading amounts to the enlistment of a fresh intermediate symbol, ${}^{\backprime \backprime }R\,{}^{\prime \prime }\in {\mathfrak {Q}},$ as a part of a new grammar for ${\mathfrak {C}}({\mathfrak {P}}).$ In effect, ${}^{\backprime \backprime }R\,{}^{\prime \prime }$ affords a grammatical recognition for any rune that forms a part of a sentence in ${\mathfrak {C}}({\mathfrak {P}}).$ In situations where these variant usages are likely to be confused, the types of strings can be indicated by means of expressions like $r<:R$ and $W<:R.$

A foil is a string of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime} \, \mathrm{(} \, {}^{\prime\prime} \, \cdot \, T \, \cdot \, {}^{\backprime\backprime} \, \mathrm{)} \, {}^{\prime\prime},} where $T$ is a tract. Thus, a typical foil Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F} has the form:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lllllllllllllll} F & = & {}^{\backprime\backprime} \, \mathrm{(} \, {}^{\prime\prime} & \cdot & S_1 & \cdot & {}^{\backprime\backprime} \mathrm{,} {}^{\prime\prime} & \cdot & \ldots & \cdot & {}^{\backprime\backprime} \mathrm{,} {}^{\prime\prime} & \cdot & S_k & \cdot & {}^{\backprime\backprime} \, \mathrm{)} \, {}^{\prime\prime} \\ \end{array}}

This is just the surcatenation of the sentences $S_{1},\ldots ,S_{k}.$ Given the possibility that this sequence of sentences is empty, and thus that the tract $T$ is the empty string, the minimum foil $F$ is the expression Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime} \, \mathrm{()} \, {}^{\prime\prime}.} Explicitly marking each foil Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F} that is embodied in a cactus expression is tantamount to recognizing another intermediate symbol, ${}^{\backprime \backprime }F\,{}^{\prime \prime }\in {\mathfrak {Q}},$ further articulating the structures of sentences and expanding the grammar for the language Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{C} (\mathfrak{P}).} All of the same remarks about the versatile uses of the intermediate symbols, as string variables and as type names, apply again to the letter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime} F \, {}^{\prime\prime}.}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{C} (\mathfrak{P}) : \text{Grammar 3}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{Q} = \{ \, {}^{\backprime\backprime} F \, {}^{\prime\prime}, \, {}^{\backprime\backprime} R \, {}^{\prime\prime}, \, {}^{\backprime\backprime} T \, {}^{\prime\prime} \, \}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{array}{rcll} 1. & S & :> & R \\ 2. & S & :> & F \\ 3. & S & :> & S \, \cdot \, S \\ 4. & R & :> & \varepsilon \\ 5. & R & :> & m_1 \\ 6. & R & :> & p_j, \, \text{for each} \, j \in J \\ 7. & R & :> & R \, \cdot \, R \\ 8. & F & :> & {}^{\backprime\backprime} \, \mathrm{(} \, {}^{\prime\prime} \, \cdot \, T \, \cdot \, {}^{\backprime\backprime} \, \mathrm{)} \, {}^{\prime\prime} \\ 9. & T & :> & S \\ 10. & T & :> & T \, \cdot \, {}^{\backprime\backprime} \mathrm{,} {}^{\prime\prime} \, \cdot \, S \\ \end{array}}

In Grammar 3, the first three Rules say that a sentence (a string of type Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S} ), is a rune (a string of type Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R} ), a foil (a string of type Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F} ), or an arbitrary concatenation of strings of these two types. Rules 4 through 7 specify that a rune Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R} is an empty string $\varepsilon ,$ a blank symbol $m_{1},$ a paint $p_{j},$ or any concatenation of strings of these three types. Rule 8 characterizes a foil $F$ as a string of the form ${}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,T\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime },$ where $T$ is a tract. The last two Rules say that a tract $T$ is either a sentence $S$ or else the concatenation of a tract, a comma, and a sentence, in that order.

At this point in the succession of grammars for ${\mathfrak {C}}({\mathfrak {P}}),$ the explicit uses of indefinite iterations, like the kleene star operator, are now completely reduced to finite forms of concatenation, but the problems that some styles of analysis have with allowing non-terminal symbols to cover both themselves and the empty string are still present.

Any degree of reflection on this difficulty raises the general question: What is a practical strategy for accounting for the empty string in the organization of any formal language that counts it among its sentences? One answer that presents itself is this: If the empty string belongs to a formal language, it suffices to count it once at the beginning of the formal account that enumerates its sentences and then to move on to more interesting materials.

Returning to the case of the cactus language ${\mathfrak {C}}({\mathfrak {P}}),$ in other words, the formal language $\mathrm {PARCE}$ of painted and rooted cactus expressions, it serves the purpose of efficient accounting to partition the language into the following couple of sublanguages:

The emptily painted and rooted cactus expressions make up the language $\mathrm {EPARCE}$ that consists of a single empty string as its only sentence. In short:

$\mathrm {EPARCE} \ =\ {\underline {\varepsilon }}\ =\ \{\varepsilon \}$
The significantly painted and rooted cactus expressions make up the language $\mathrm {SPARCE}$ that consists of everything else, namely, all of the non-empty strings in the language $\mathrm {PARCE} .$ In sum:

$\mathrm {SPARCE} \ =\ \mathrm {PARCE} \setminus \varepsilon$

As a result of marking the distinction between empty and significant sentences, that is, by categorizing each of these three classes of strings as an entity unto itself and by conceptualizing the whole of its membership as falling under a distinctive symbol, one obtains an equation of sets that connects the three languages being marked:

\mathrm {SPARCE} \ =\ \mathrm {PARCE} \ -\ \mathrm {EPARCE}

In sum, one has the disjoint union:

\mathrm {PARCE} \ =\ \mathrm {EPARCE} \ \cup \ \mathrm {SPARCE}

For brevity in the present case, and to serve as a generic device in any similar array of situations, let $S$ be the type of an arbitrary sentence, possibly empty, and let $S'$ be the type of a specifically non-empty sentence. In addition, let ${\underline {\varepsilon }}$ be the type of the empty sentence, in effect, the language ${\underline {\varepsilon }}=\{\varepsilon \}$ that contains a single empty string, and let a plus sign ${}^{\backprime \backprime }+{}^{\prime \prime }$ signify a disjoint union of types. In the most general type of situation, where the type $S$ is permitted to include the empty string, one notes the following relation among types:

S\ =\ {\underline {\varepsilon }}\ +\ S'

With the distinction between empty and significant expressions in mind, I return to the grasp of the cactus language ${\mathfrak {L}}={\mathfrak {C}}({\mathfrak {P}})=\mathrm {PARCE} ({\mathfrak {P}})$ that is afforded by Grammar 2, and, taking that as a point of departure, explore other avenues of possible improvement in the comprehension of these expressions. In order to observe the effects of this alteration as clearly as possible, in isolation from any other potential factors, it is useful to strip away the higher levels intermediate organization that are present in Grammar 3, and start again with a single intermediate symbol, as used in Grammar 2. One way of carrying out this strategy leads on to a grammar of the variety that will be articulated next.

Grammar 4

If one imposes the distinction between empty and significant types on each non-terminal symbol in Grammar 2, then the non-terminal symbols ${}^{\backprime \backprime }S\,{}^{\prime \prime }$ and ${}^{\backprime \backprime }T\,{}^{\prime \prime }$ give rise to the expanded set of non-terminal symbols ${}^{\backprime \backprime }S\,{}^{\prime \prime },\,{}^{\backprime \backprime }S'\,{}^{\prime \prime },\,{}^{\backprime \backprime }T\,{}^{\prime \prime },\,{}^{\backprime \backprime }T'\,{}^{\prime \prime },$ leaving the last three of these to form the new intermediate alphabet. Grammar 4 has the intermediate alphabet Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{Q} \, = \, \{ \, {}^{\backprime\backprime} S' \, {}^{\prime\prime}, \, {}^{\backprime\backprime} T \, {}^{\prime\prime}, \, {}^{\backprime\backprime} T' \, {}^{\prime\prime} \, \},} with the set ${\mathfrak {K}}$ of covering rules as listed in the next display.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{C} (\mathfrak{P}) : \text{Grammar 4}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{Q} = \{ \, {}^{\backprime\backprime} S' \, {}^{\prime\prime}, \, {}^{\backprime\backprime} T \, {}^{\prime\prime}, \, {}^{\backprime\backprime} T' \, {}^{\prime\prime} \, \}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{array}{rcll} 1. & S & :> & \varepsilon \\ 2. & S & :> & S' \\ 3. & S' & :> & m_1 \\ 4. & S' & :> & p_j, \, \text{for each} \, j \in J \\ 5. & S' & :> & {}^{\backprime\backprime} \, \mathrm{(} \, {}^{\prime\prime} \, \cdot \, T \, \cdot \, {}^{\backprime\backprime} \, \mathrm{)} \, {}^{\prime\prime} \\ 6. & S' & :> & S' \, \cdot \, S' \\ 7. & T & :> & \varepsilon \\ 8. & T & :> & T' \\ 9. & T' & :> & T \, \cdot \, {}^{\backprime\backprime} \mathrm{,} {}^{\prime\prime} \, \cdot \, S \\ \end{array}}

In this version of a grammar for ${\mathfrak {L}}={\mathfrak {C}}({\mathfrak {P}}),$ the intermediate type Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T} is partitioned as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T = \underline\varepsilon + T',} thereby parsing the intermediate symbol Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T} in parallel fashion with the division of its overlying type as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S = \underline\varepsilon + S'.} This is an option that I will choose to close off for now, but leave it open to consider at a later point. Thus, it suffices to give a brief discussion of what it involves, in the process of moving on to its chief alternative.

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q \in \{ \, {}^{\backprime\backprime} S \, {}^{\prime\prime} \, \} \cup \mathfrak{Q}} and sentential forms Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W \in \{ \, {}^{\backprime\backprime} S \, {}^{\prime\prime} \, \} \cup (\mathfrak{Q} \cup \mathfrak{A})^*.}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \text{Condition On Intermediate Significance}}

${\begin{array}{lccc}{\text{If}}&q&:>&W\\{\text{and}}&W&=&\varepsilon \\{\text{then}}&q&=&{}^{\backprime \backprime }S\,{}^{\prime \prime }\\\end{array}}$

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, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime}\!< \, {}^{\prime\prime}.}

The ordering Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime}\!< \, {}^{\prime\prime}} on the set of non-terminal symbols, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q \in \{ \, {}^{\backprime\backprime} S \, {}^{\prime\prime} \, \} \cup \mathfrak{Q},} ordains the initial symbol Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime} S \, {}^{\prime\prime}} to be strictly prior to every intermediate symbol. This is tantamount to the axiom that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime} S \, {}^{\prime\prime} < q,} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q \in \mathfrak{Q}.}
The ordering Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime}\!< \, {}^{\prime\prime}} on the collection of sentential forms, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W \in \{ \, {}^{\backprime\backprime} S \, {}^{\prime\prime} \, \} \cup (\mathfrak{Q} \cup \mathfrak{A})^*,} ordains the empty string to be strictly minor to every other sentential form. This is stipulated in the axiom that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \varepsilon < W,} for every non-empty sentential form $W.$

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

${\text{Condition On Intermediate Significance}}$

${\begin{array}{lccc}{\text{If}}&q&:>&W\\{\text{and}}&q&>&{}^{\backprime \backprime }S\,{}^{\prime \prime }\\{\text{then}}&W&>&\varepsilon \\\end{array}}$

Achieving a grammar that respects this convention typically requires a more detailed account of the initial setting of a type, both with regard to the type of context that incites its appearance and also with respect to the minimal strings that arise under the type in question. In order to find covering productions that satisfy the intermediate significance condition, one must be prepared to consider a wider variety of calling contexts or inciting situations that can be noted to surround each recognized type, and also to enumerate a larger number of the smallest cases that can be observed to fall under each significant type.

Grammar 5

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

${\begin{array}{ccll}S&:>&\varepsilon &\\q&:>&W,&{\text{with}}\ q\in \{\,{}^{\backprime \backprime }S\,{}^{\prime \prime }\,\}\cup {\mathfrak {Q}}\ {\text{and}}\ W\in ({\mathfrak {Q}}\cup {\mathfrak {A}})^{+}\\\end{array}}$

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:>\varepsilon ,$ 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 that uses ${\mathfrak {Q}}=\{\,{}^{\backprime \backprime }S'\,{}^{\prime \prime },\,{}^{\backprime \backprime }T\,{}^{\prime \prime }\,\},$ with ${\mathfrak {K}}$ as listed in the next display.

${\mathfrak {C}}({\mathfrak {P}}):{\text{Grammar 5}}$

${\mathfrak {Q}}=\{\,{}^{\backprime \backprime }S'\,{}^{\prime \prime },\,{}^{\backprime \backprime }T\,{}^{\prime \prime }\,\}$

${\begin{array}{rcll}1.&S&:>&\varepsilon \\2.&S&:>&S'\\3.&S'&:>&m_{1}\\4.&S'&:>&p_{j},\,{\text{for each}}\,j\in J\\5.&S'&:>&S'\,\cdot \,S'\\6.&S'&:>&{}^{\backprime \backprime }\,\mathrm {()} \,{}^{\prime \prime }\\7.&S'&:>&{}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,T\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\\8.&T&:>&{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\\9.&T&:>&S'\\10.&T&:>&T\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\\11.&T&:>&T\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,S'\\\end{array}}$

Finally, it is worth trying to bring together the advantages of these diverse styles of grammar, to whatever extent that they are compatible. To do this, a prospective grammar must be capable of maintaining a high level of intermediate organization, like that arrived at in Grammar 2, while respecting the principle of intermediate significance, and thus accumulating all the benefits of the context-free format in Grammar 5. A plausible synthesis of most of these features is given in Grammar 6.

Grammar 6

Grammar 6 has the intermediate alphabet ${\mathfrak {Q}}=\{\,{}^{\backprime \backprime }S'\,{}^{\prime \prime },\,{}^{\backprime \backprime }F\,{}^{\prime \prime },\,{}^{\backprime \backprime }R\,{}^{\prime \prime },\,{}^{\backprime \backprime }T\,{}^{\prime \prime }\,\},$ with the production set ${\mathfrak {K}}$ as listed in the next display.

${{\mathfrak {C}}({\mathfrak {P}}):{\text{Grammar 6}}}$

${\mathfrak {Q}}=\{\,{}^{\backprime \backprime }S'\,{}^{\prime \prime },\,{}^{\backprime \backprime }F\,{}^{\prime \prime },\,{}^{\backprime \backprime }R\,{}^{\prime \prime },\,{}^{\backprime \backprime }T\,{}^{\prime \prime }\,\}$

${\begin{array}{rcll}1.&S&:>&\varepsilon \\2.&S&:>&S'\\3.&S'&:>&R\\4.&S'&:>&F\\5.&S'&:>&S'\,\cdot \,S'\\6.&R&:>&m_{1}\\7.&R&:>&p_{j},\,{\text{for each}}\,j\in J\\8.&R&:>&R\,\cdot \,R\\9.&F&:>&{}^{\backprime \backprime }\,\mathrm {()} \,{}^{\prime \prime }\\10.&F&:>&{}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,T\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }\\11.&T&:>&{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\\12.&T&:>&S'\\13.&T&:>&T\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\\14.&T&:>&T\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,S'\\\end{array}}$

The preceding development provides a typical example of how an initially effective and conceptually succinct description of a formal language, but one that is terse to the point of allowing its prospective interpreter to waste exorbitant amounts of energy in trying to unravel its implications, can be converted into a form that is more efficient from the operational point of view, even if slightly more ungainly in regard to its elegance.

The basic idea behind all of this machinery remains the same: Besides the select body of formulas that are introduced as boundary conditions, it merely institutes the following general rule:

$\mathrm {If}$	the strings $S_{1},\ldots ,S_{k}$ are sentences,
$\mathrm {Then}$	their concatenation in the form
	$\mathrm {Conc} _{j=1}^{k}S_{j}\ =\ S_{1}\,\cdot \,\ldots \,\cdot \,S_{k}$
	is a sentence,
$\mathrm {And}$	their surcatenation in the form
	$\mathrm {Surc} _{j=1}^{k}S_{j}\ =\ {}^{\backprime \backprime }\,\mathrm {(} \,{}^{\prime \prime }\,\cdot \,S_{1}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,\ldots \,\cdot \,{}^{\backprime \backprime }\,\mathrm {,} \,{}^{\prime \prime }\,\cdot \,S_{k}\,\cdot \,{}^{\backprime \backprime }\,\mathrm {)} \,{}^{\prime \prime }$
	is a sentence.

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:

${}^{\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.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{Q} = \{ q_1, \ldots, q_m \}} is a finite set of intermediate symbols, all distinct from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime} S \, {}^{\prime\prime}.}
${\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime} S \, {}^{\prime\prime}} and disjoint from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{Q}.} Depending on the particular conception of the language Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{L}} that is covered, generated, governed, or ruled by the grammar Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G},} that is, whether Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G}} and the language Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{L}} that it regulates.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{K}} it helps to define some additional terms:

The symbols in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{ \, {}^{\backprime\backprime} S \, {}^{\prime\prime} \, \} \cup \mathfrak{Q} \cup \mathfrak{A}} form the augmented alphabet of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G}.}
The symbols in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{ \, {}^{\backprime\backprime} S \, {}^{\prime\prime} \, \} \cup \mathfrak{Q}} are the non-terminal symbols of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G}.}
The symbols in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{Q} \cup \mathfrak{A}} are the non-initial symbols of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G}.}
The strings in $(\{\,{}^{\backprime \backprime }S\,{}^{\prime \prime }\,\}\cup {\mathfrak {Q}}\cup {\mathfrak {A}})^{*}$ are the augmented strings for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G}.}
The strings in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{ \, {}^{\backprime\backprime} S \, {}^{\prime\prime} \, \} \cup (\mathfrak{Q} \cup \mathfrak{A})^*} are the sentential forms for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G}.}

Each characterization in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q1 \cdot W \cdot Q2,} in effect, replacing the non-terminal symbol $q$ with the non-initial string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W} in any selected, preserved, and closely adjoining context of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q1 \cdot \underline{~~~} \cdot Q2.} In this application the notation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1 :> S_2} can be read to say that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1} produces Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_2} or that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1} transforms into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_2.}

An immediate derivation in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G}} is an ordered pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (W, W^\prime)} of sentential forms in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G}} such that:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (X, Y) \in \mathfrak{K}} by writing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X :> Y \, \text{in} \, \mathfrak{G}.}

The immediate derivation relation is indicated by saying that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W} immediately derives Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W',} by saying that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W'} is immediately derived from $W$ in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G},} and also by writing:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{L} = \mathfrak{L} (\mathfrak{G}) = \langle \mathfrak{G} \rangle} that is generated by the formal grammar Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{G} = ( \, {}^{\backprime\backprime} S \, {}^{\prime\prime}, \, \mathfrak{Q}, \, \mathfrak{A}, \, \mathfrak{K} \, )} is the set of strings over the terminal alphabet Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{A}} that are derivable from the initial symbol Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {}^{\backprime\backprime} S \, {}^{\prime\prime}} by way of the intermediate symbols in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{Q}} according to the characterizations in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{K}.} In sum:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak{L} (\mathfrak{G}) \ = \ \langle \mathfrak{G} \rangle \ = \ \{ \, W \in \mathfrak{A}^* \, : \, {}^{\backprime\backprime} S \, {}^{\prime\prime} \, :\!*\!:> \, W \, \}.}

Finally, a string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W} is called a word, a sentence, or so on, of the language generated by ${\mathfrak {G}}$ if and only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W} is in ${\mathfrak {L}}({\mathfrak {G}}).$

• Overview • Part 1 • Part 2 • Part 3 • Part 4 • Part 5 • Part 6 • Part 7 • Part 8 • Part 9 • Part 10 • Part 11 • Part 12 • Part 13 • Part 14 • Part 15 • Part 16 • Appendix A1 • Appendix A2 • References • Document History •

Inquiry Driven Systems • Part 3

Contents

Cactus Language • 1

Syntax

Grammar 1

Grammar 2

Grammar 3

Grammar 4

Grammar 5

Grammar 6

Generalities About Formal Grammars

Navigation menu

Views

Personal tools

Navigation

Search

Tools