## Links forward

### More examples of functions

#### A function defined on a language

The study of formal languages is an important part of theoretical computer science.

Let \(\Sigma\) be a finite set of symbols. In computer science, this is often called an **alphabet**. For example, we could take \(\Sigma=\{a,b,c,\dots,z\}\) or \(\Sigma=\{a,b\}\).

A **word** over \(\Sigma\) is a finite string of characters from \(\Sigma\). For example, if \(\Sigma=\{a,b\}\), then the following are examples of words over \(\Sigma\):

The **empty word**, which has no characters, is denoted by \(\varepsilon\). Let \(\Sigma^*\) be the set of all words over \(\Sigma\).

The **length** of a word is the number of characters in the string. Thus, for example,

This gives us a natural function \(l\colon \Sigma^*\to \mathbb{N} \cup \{0\}\).

The function \(l\) induces a natural partition on the set of all words over \(\Sigma\). Define \(\Sigma^i\) to be all words of length \(i\), that is,

\[ \Sigma^i = \{\, w \in \Sigma^* : l(w) = i \,\}. \]Then we can write \(\Sigma^*\) as the disjoint union

\[ \Sigma^* = \bigcup_{i=0}^\infty \Sigma^i. \]#### Binary operations as functions

There are four basic binary operations involving the real numbers:

\[ 3+2=5, \qquad 3-2=1, \qquad 3\times 2=6, \qquad 3\div 2=\dfrac{3}{2}. \]All of these can be thought of as functions. For example,

\[ +\colon \mathbb{R}\times\mathbb{R} \to \mathbb{R},\qquad (a,b) \mapsto a+b. \]We can also consider the restrictions \(+ \colon \mathbb{Z}\times\mathbb{Z} \to \mathbb{Z}\) and \(+\colon \mathbb{Q}\times\mathbb{Q}\). This idea is a starting point for abstract algebra.

#### Probability distributions as functions

Consider a finite sample space \(\mathcal{E} = \{a_1,a_2,a_3,\dots,a_n\}\). Let \(\mathcal{P}(\mathcal{E})\) denote the set of all subsets of \(\mathcal{E}\), that is, the set of all events. (The notation \(\mathcal{P}\) is used because 'the set of all subsets of \(S\)' is called the **power set** of \(S\).) Then we can assign probabilities to events by a function

that satisfies \(\Pr(\mathcal{E})=1\) and \(\Pr(A) = \displaystyle\sum_{a\in A}\Pr(\{a\})\), for all \(A \subseteq \mathcal{E}\). See the module Probability .