### 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$$:

$a,\qquad b, \qquad ab,\qquad bbb,\qquad aababbab.$

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,

$l(\varepsilon)=0,\qquad l(a)=l(b)=1,\qquad l(abab)=4.$

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

$\mathrm{Pr} \colon \mathcal{P}(\mathcal{E}) \to [0,1]$

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 .

Next page - History