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\):

\[ 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