This site is supported by donations to The OEIS Foundation.

Cactus Language • Part 2

From OeisWiki
Jump to: navigation, search

Author: Jon Awbrey

OverviewPart 1Part 2Part 3ReferencesDocument 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 four-tuple that takes the following form of description:

  1. 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.
  2. is a finite set of intermediate symbols, all distinct from
  3. 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.
  4. 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:

  1. The symbols in form the augmented alphabet of
  2. The symbols in are the non-terminal symbols of
  3. The symbols in are the non-initial symbols of
  4. The strings in are the augmented strings for
  5. 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 non-empty string and a sentential form over while is a possibly empty string and also a sentential form over

Here also, is a non-terminal symbol, that is, while and are possibly empty strings of non-initial 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 non-terminal symbol with the non-initial 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

OverviewPart 1Part 2Part 3ReferencesDocument History