Cactus Language • Preliminaries 3

A few definitions from formal language theory are required at this point.

An alphabet is a finite set of signs, typically, $\mathfrak{A} = \{ \mathfrak{a}_1, \ldots, \mathfrak{a}_n \}.$

A string over an alphabet $\mathfrak{A}$ is a finite sequence of signs from $\mathfrak{A}.$

The length of a string is just its length as a sequence of signs.

The empty string is the unique sequence of length 0. It is sometimes denoted by an empty pair of quotation marks, “”, but more often by the Greek symbols epsilon or lambda.

A sequence of length $k > 0$ is typically presented in the following concatenated forms.

$s_1 s_2 \ldots s_{k-1} s_k$

$s_1 \cdot s_2 \cdot \ldots \cdot s_{k-1} \cdot s_k$

with $s_j \in \mathfrak{A}$ for all $j = 1 \ldots k.$

The following notations provide useful alternatives.

$\varepsilon$ = “” = the empty string.

$\underline\varepsilon$ = $\{ \varepsilon \}$ = the language consisting of a single empty string.

Several operations on strings find sufficient application to motivate the following definitions.

To erase an appearance of a sign is to replace it with an appearance of the blank symbol “ ”.

To delete an appearance of a sign is to replace it with an appearance of the empty string “”.

If $s$ is a string which ends with a sign $t$ then $s \cdot t^{-1}$ is the string which results by deleting the terminal $t$ from $s.$

A token is a particular appearance of a sign.

Finally —

The kleene star $\mathfrak{A}^*$ of alphabet $\mathfrak{A}$ is the set of all strings over $\mathfrak{A}.$ In particular, $\mathfrak{A}^*$ includes among its elements the empty string $\varepsilon.$

The kleene plus $\mathfrak{A}^+$ of an alphabet $\mathfrak{A}$ is the set of all positive length strings over $\mathfrak{A},$ in other words, everything in $\mathfrak{A}^*$ but the empty string.

A formal language $\mathfrak{L}$ over an alphabet $\mathfrak{A}$ is a subset of $\mathfrak{A}^*.$ In brief, $\mathfrak{L} \subseteq \mathfrak{A}^*.$ If $s$ is a string over $\mathfrak{A}$ and $s$ is an element of $\mathfrak{L}$ then it is customary to call $s$ a sentence of $\mathfrak{L}.$ Thus, a formal language $\mathfrak{L}$ is defined by specifying its elements, which amounts to saying what it means to be a sentence of $\mathfrak{L}.$

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