Some Definitions regarding Language

Because the automata of the following sections will deal with input consisting of strings of symbols from an alphabet, we will introduce here some technical terms to describe this kind of input.

Following Hopcroft & Ullman (1979) [137] we will not define the term symbol but presuppose, that there is some agreement possible, what is meant by a symbol (that disciplin, which could be asked here for a more broader explanation, would be semiotics (cf. as an introduction Noeth (2000) [220])). Examples of symbols are letters and digits. We think of an alphabet $\Sigma$ as a finite set of distinguished symbols, e.g. {a,b,c,d,e,1,2,3,4,5,6,7,8,9,0}. To combine elements like 'a', 'b', and 'c' of an alphabet $\Sigma$ to a sequence like 'abc' we say, that the elements have been concatenated. The result of a concatenation is always a string of symbols or a word. The length of a string w -written as $\mid$w$\mid$- is the number of elements in this string; e.g. $\mid$abc$\mid$ = 3. It is common to denote the empty string by $\epsilon$ with the meaning $\mid\epsilon\mid$ = 0. The concatenation of two strings w and v -written as wv- is realized by connecting the two strings directly. It holds that $\epsilon$w = w$\epsilon$ = w for each string w. A language is a set of strings over an alphabet. Here one has to distinguish the empty set = $\varnothing$ = {} and the set containing the empty string $\epsilon$ as {$\epsilon$}. {} $\not=$ {$\epsilon$}.

The set of all finite words on the alphabet $\Sigma$ is written $\Sigma^{\star}$, which represents a free monoid on $\Sigma$. In algebra is a monoid -or semigroup- a set M with a binary operation $\bullet$: M $\times$ M $\longrightarrow$ M, obeying the following axioms:

1. Associativity: for all a, b, c $in$ M, (a$\bullet$b)$\bullet$c = a$\bullet$(b$\bullet$c)
2. Identity element: there exists an element e $in$ M, such that for all a $in$ M, a$\bullet$e = e$\bullet$a = a.

For automata which run continously one needs input strings of infinite length. These inputs can be provided with $\omega$-languages (cf. Farwer (2002) [100]). For this one sets $\omega$ = $Natural Numbers$ including '0'. While $\Sigma$ denotes a finite set of symbols representing an alphabet and $\Sigma^{\star}$ denotes the set of possible finite words on $\Sigma$, $\Sigma^{\omega}$ denotes the set of infinite words (or: $\omega$-word) on $\Sigma$ (the cardinality of $\Sigma^{\star}$ is countably infinite, but the cardinality of $\Sigma^{\omega}$ is uncountable infinite!). Each word $\alpha \in \Sigma^{\omega}$ has length $\mid\alpha\mid$ = $\omega$. One convention is to write $\omega$-words like $\alpha = \alpha(0)\alpha(1)...$ with $\alpha(i) \in \Sigma$. A set of $\omega$-words over a given alphabet is called an $\omega$-language. One denotes the number of occurences of a in $\alpha$ as $\mid\alpha\mid_{a}$. Furthermore it is defined for an $\omega$-word $\alpha \in \Sigma^{\omega}$

$$Occ(\alpha) = \{\alpha \in \Sigma \mid \exists i \alpha(i) = a \}$$

the -possibly finite- set of letters a occuring in $\alpha$, and with

$$Inf(\alpha) = \{\alpha \in \Sigma \mid \forall i\exists j \geq (i+1) \alpha(j) = a \}$$

the -possibly finite- set of letters a occuring in $\alpha$ infinitely often.