Generalities About Formal Grammars • 2

Characterizations

Recall that a formal grammar $\mathfrak{G}$ is defined by a 4‑tuple $\mathfrak{G} = ( ``S", \mathfrak{Q}, \mathfrak{A}, \mathfrak{K} )$ where $``S"$ is the initial, special, start, or sentence symbol, $\mathfrak{Q}$ is a finite set of intermediate symbols, $\mathfrak{A}$ is a finite set of terminal symbols, also known as the alphabet of $\mathfrak{G},$ and $\mathfrak{K}$ is a finite set of characterizations, variously described as covering rules, formations, productions, rewrite rules, subsumptions, transformations, or typing rules.

To describe the variety of elements in $\mathfrak{K}$ it helps to define a few additional terms.

Augmented Alphabet: The symbols in $\{ ``S" \} \cup \mathfrak{Q} \cup \mathfrak{A}$ form the augmented alphabet of $\mathfrak{G}.$
Non‑Terminal Symbols: The symbols in $\{ ``S" \} \cup \mathfrak{Q}$ are the non‑terminal symbols of $\mathfrak{G}.$
Non‑Initial Symbols: The symbols in $\mathfrak{Q} \cup \mathfrak{A}$ are the non‑initial symbols of $\mathfrak{G}.$
Augmented Strings: The strings in $( \{ ``S" \} \cup \mathfrak{Q} \cup \mathfrak{A} )^*$ are the augmented strings for $\mathfrak{G}.$
Sentential Forms: The strings in $\{ ``S" \} \cup (\mathfrak{Q} \cup \mathfrak{A})^*$ are the sentential forms for $\mathfrak{G}.$

Each member of $\mathfrak{K}$ is an ordered pair of strings $(S_1, S_2)$ taking the following form.

$\begin{matrix} S_1 & = & Q_1 \cdot q \cdot Q_2 \\[8pt] S_2 & = & Q_1 \cdot W \cdot Q_2 \end{matrix}$

$S_1$ and $S_2$ are augmented strings for $\mathfrak{G},$ in particular, sentential forms with $S_1$ being a non‑empty string and $S_2$ being a possibly empty string.

The element $q$ is a non‑terminal symbol, in other words, $q \in \{ ``S" \} \cup \mathfrak{Q}.$ The elements $Q_1, Q_2,$ and $W$ are possibly empty strings of non‑initial symbols, that is to say, $Q_1, Q_2, W \in (\mathfrak{Q} \cup \mathfrak{A})^*.$

In practice the couplets belonging to $\mathfrak{K}$ are used to derive, generate, or 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 expressed in the form $\mathfrak{L} = \langle \mathfrak{G} \rangle.$

Because it helps to focus our attention on the the more active dynamic aspects of using grammars to generate languages it is usual to write abstract characterizations like $(S_1, S_2)$ and specific characterizations like $(Q_1 \cdot q \cdot Q_2, \ Q_1 \cdot W \cdot Q_2)$ in the following forms.

$\begin{matrix} S_1 & :> & S_2 \\[8pt] Q_1 \cdot q \cdot Q_2 & :> & Q_1 \cdot W \cdot Q_2 \end{matrix}$

The characterization $S_1 :> S_2$ amounts to a grammatical license to transform a string of the form $Q_1 \cdot q \cdot Q_2$ into a string of the form $Q_1 \cdot W \cdot Q_2,$ in effect, replacing the non‑terminal symbol $q$ with the non‑initial string $W$ in any selected, preserved, and closely adjoining context of the form $Q_1 \cdot \underline{~~~} \cdot Q_2.$ In that application the notation $S_1 :> S_2$ can be read to say that $S_1$ produces $S_2$ or that $S_1$ transforms into $S_2.$

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	31