This site is supported by donations to The OEIS Foundation.
Cactus Language • Part 2
Author: Jon Awbrey
• Overview • Part 1 • Part 2 • Part 3 • References • Document History •
The Cactus Patch (cont.)
Generalities About Formal Grammars
It is fitting to wrap up the foregoing developments by summarizing the notion of a formal grammar that appeared to evolve in the present case. For the sake of future reference and the chance of a wider application, it is also useful to try to extract the scheme of a formalization that potentially holds for any formal language. The following presentation of the notion of a formal grammar is adapted, with minor modifications, from the treatment in (DDQ, 60–61).
A formal grammar is given by a fourtuple that takes the following form of description:
 is the initial, special, start, or sentence symbol. Since the letter 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.
 is a finite set of intermediate symbols, all distinct from
 is a finite set of terminal symbols, also known as the alphabet of all distinct from and disjoint from Depending on the particular conception of the language that is covered, generated, governed, or ruled by the grammar that is, whether is conceived to be a set of words, sentences, paragraphs, or more extended structures of discourse, it is usual to describe as the alphabet, lexicon, vocabulary, liturgy, or phrase book of both the grammar and the language that it regulates.
 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 it helps to define some additional terms:
 The symbols in form the augmented alphabet of
 The symbols in are the nonterminal symbols of
 The symbols in are the noninitial symbols of
 The strings in are the augmented strings for
 The strings in are the sentential forms for
Each characterization in is an ordered pair of strings that takes the following form:
In this scheme, and are members of the augmented strings for more precisely, is a nonempty string and a sentential form over while is a possibly empty string and also a sentential form over
Here also, is a nonterminal symbol, that is, while and are possibly empty strings of noninitial symbols, a fact that can be expressed in the form,
In practice, the couplets in are used to derive, to generate, or to produce sentences of the corresponding language The language is then said to be governed, licensed, or regulated by the grammar a circumstance that is expressed in the form In order to facilitate this active employment of the grammar, it is conventional to write the abstract characterization and the specific characterization in the following forms, respectively:

In this usage, the characterization is tantamount to a grammatical license to transform a string of the form into a string of the form in effect, replacing the nonterminal symbol with the noninitial string in any selected, preserved, and closely adjoining context of the form In this application the notation can be read to say that produces or that transforms into
An immediate derivation in is an ordered pair of sentential forms in such that:

As noted above, it is usual to express the condition by writing
The immediate derivation relation is indicated by saying that immediately derives by saying that is immediately derived from in and also by writing:
A derivation in is a finite sequence of sentential forms over such that each adjacent pair of sentential forms in the sequence is an immediate derivation in in other words, such that:
If there exists a derivation in one says that derives in or that is derivable from in and one typically summarizes the derivation by writing:
The language that is generated by the formal grammar is the set of strings over the terminal alphabet that are derivable from the initial symbol by way of the intermediate symbols in according to the characterizations in In sum:
Finally, a string is called a word, a sentence, or so on, of the language generated by if and only if is in
• Overview • Part 1 • Part 2 • Part 3 • References • Document History •
 Adaptive systems
 Artificial intelligence
 Boolean algebra
 Boolean functions
 Category theory
 Combinatorics
 Computation theory
 Cybernetics
 Differential logic
 Discrete systems
 Dynamical systems
 Formal languages
 Formal sciences
 Formal systems
 Functional logic
 Graph theory
 Group theory
 Logic
 Logical graphs
 Neural networks
 Peirce, Charles Sanders
 Semiotics
 Systems theory
 Visualization