The Language of Computation

Definitions

• alphabet: An alphabet is any non-empty, finite set of symbols
  • binary alphabet: ${\sum }_{bool}=\{0,1\}$
  • decimal digits: ${\sum }_{dec}=\{0,1,\dots ,9\}$
• word: A word over an alphabet $\sum$ is a finite sequence of symbols from $\sum$.
  • empty word: $|\lambda |=0$
• ${\sum }^{\ast }$ is the set of all words over $\sum$
• ${\sum }^{+}={\sum }^{\ast }-\{\lambda \}$

Number

$x=x_1{x}_2\dots x_n\in {\sum }_{bool}^{\ast }$

$Nummer(x)={\sum }_{i=1}^n{x}_i\cdot 2^{n-i}$

For $m\in (\mathbb{N}-\{0\})$ , $Bin(m)$ is the binary expression without zeros in the front $Bin(0)=0$

concatenation

$kon:{\sum }^{\ast }\times {\sum }^{\ast }\to {\sum }^{\ast }$ with $kon(x,y)=xy=x\cdot y$ Example $x=01,y=11$ we get $xy=0111$

reverse

let $w={\alpha }_1{\alpha }_2\dots {\alpha }_n$ $w^R={\alpha }_n{\alpha }_{n-1}\dots {\alpha }_1$

iteration

let $x\in {\sum }^{\ast },i\in \mathbb{N}$ the $i$-th iteration of $x$ is:

• $x^0=\lambda$
• $x^1=x$
• $x^i=x{x}^{i-1}$ Example: $x=ab$, $x^3=ababab$

deconstruction

Let $v,w\in {\sum }^{\ast }$ for alphabet $\sum$

• $v$ is a subword (substring) of $w$ if: $\exists x,y\in {\sum }^{\ast }:w=xvy$
• $v$ is a prefix of $w$ if: $\exists y\in {\sum }^{\ast }:w=vy$
• $v$ is a suffix of $w$ if: $\exists y\in {\sum }^{\ast }:w=xv$

occurrence

For $x\in {\sum }^{\ast },\alpha \in \sum$ $|x{|}_{\alpha }$ is the number of occurrence of $\alpha$ in $x$

order

Let $\sum =\{s_1,\dots ,s_m\}$ with $s_1<s_2<\cdots <s_m$ The canonical order is defined as $u<v⟺(|u|<|v|)\vee (|u|=|v|\wedge u=s_i{u}^{\prime },v=s_j{v}^{\prime }\text{ with }i<j$

In text:

1. First, order words by length, with shorter words coming first.
2. For words of the same length, order them lexicographically (like in a dictionary).