Generalities About Formal Grammars • 1

It is fitting to wrap up the foregoing developments by summarizing the notion of a formal grammar which appeared to evolve in the analysis of cactus languages. For the sake of future reference and further application it is useful to extract a scheme of formalization potentially holding for arbitrary formal languages.

The following presentation is adapted with minor modifications from the treatment in Denning, Dennis, and Qualitz (1978), Machines, Languages, and Computation, Prentice–Hall, Englewood Cliffs, NJ, (pp. 60–61).

Formal Grammar • Definition

A formal grammar $\mathfrak{G}$ is defined by a four‑tuple $\mathfrak{G} = ( ``S", \mathfrak{Q}, \mathfrak{A}, \mathfrak{K} )$ of the following form.

$``S"$ is the initial, special, start, or sentence symbol. The letter $``S"$ plays that role solely in a special setting, so its employment as such creates no conflict with its possible use as a string variable or a sentence variable.

$\mathfrak{Q} = \{ q_1, \ldots, q_m \}$ is a finite set of intermediate symbols, all distinct from $``S".$

$\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 $``S"$ and disjoint from $\mathfrak{Q}.$ Depending on the particular conception of the language $\mathfrak{L}$ covered, generated, governed, or ruled by the grammar $\mathfrak{G},$ that is, whether $\mathfrak{L}$ is conceived to be a set of words, sentences, paragraphs, or more extended structures of discourse, it is usual to describe $\mathfrak{A}$ as the alphabet, lexicon, vocabulary, liturgy, or phrase book of both the grammar $\mathfrak{G}$ and the language $\mathfrak{L}$ it regulates.

$\mathfrak{K}$ is a finite set of characterizations. Depending on how they come into play, the elements of $\mathfrak{K}$ may be described as covering rules, formations, productions, rewrite rules, subsumptions, transformations, or typing rules.

Resources

cc: Academia.edu • BlueSky • Laws of Form • Ma^thstodon • Research Gate
cc: Conceptual Graphs • Cybernetics • Structural Modeling • Systems Science

	Survey of Semiotics,… on Sign Relations • Semiotic Equi…
	Survey of Semiotics,… on Sign Relations • Semiotic Equi…
	Sign Relations • Sem… on Survey of Semiotics, Semiosis,…
	Survey of Semiotics,… on Sign Relations • Semiotic Equi…
	Sign Relations • Sem… on Survey of Semiotics, Semiosis,…
	Sign Relations • Sem… on Survey of Semiotics, Semiosis,…
	Survey of Semiotics,… on Sign Relations • Semiotic Equi…
	Sign Relations • Sem… on Survey of Semiotics, Semiosis,…
	Survey of Semiotics,… on Systems of Interpretation •…
	Survey of Semiotics,… on Sign Relations, Triadic Relati…

M	T	W	T	F	S	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30