Generalities About Formal Grammars • 3

Derivations

An immediate derivation in $\mathfrak{G}$ is an ordered pair $(W, W^\prime)$ of sentential forms in $\mathfrak{G}$ such that the following conditions hold.

$\begin{array}{lll} 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 $(X, Y) \in \mathfrak{K}$ by writing $X :> Y ~\text{in}~ \mathfrak{G}.$

The immediate derivation relation is indicated by saying that $W$ immediately derives $W',$ by saying that $W'$ is immediately derived from $W$ in $\mathfrak{G},$ and also by writing the following form.

$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 the following holds.

$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 the following.

$W_1 :\!*\!:> W_k.$

The language $\mathfrak{L} = \mathfrak{L} (\mathfrak{G}) = \langle \mathfrak{G} \rangle$ generated by the formal grammar $\mathfrak{G} = ( ``S", \mathfrak{Q}, \mathfrak{A}, \mathfrak{K} )$ is the set of strings over the terminal alphabet $\mathfrak{A}$ derivable from the initial symbol $``S"$ by way of the intermediate symbols in $\mathfrak{Q}$ according to the characterizations in $\mathfrak{K}.$ All that is summed up in the following form.

$\mathfrak{L} (\mathfrak{G}) = \langle \mathfrak{G} \rangle = \{ W \in \mathfrak{A}^* : ``S" :\!*\!:> W \}.$

Finally, a string $W$ is called a word, a sentence, or so on, of the language generated by $\mathfrak{G}$ if and only if $W$ is in $\mathfrak{L} (\mathfrak{G}).$

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