Chapter 2. Formal languages

As in the case of programs such algorithms are typically created for solving not a particular task, but a group of tasks. The input, output and other related objects - e.g. the algorithm itself - should be defined and used in some general way. To do this we need some basic concepts and results in the theory of formal languages.

We start with some definitions related to functions.

Definition 2.1.

Let  and  be two arbitrary non-empty sets. 
The Cartesian product of the two sets is the set  
containing pairs from the base sets. 
If , then we may use the notation.

Let . The set  is called a relation defined on . 
If for some  and  we have , then we say that
 and are in relation by 
            
         .

Let  be a relation. If  and  the 
property  implies , then  is called 
a (partial) function and is denoted by 
         . If , then we
use the traditional notation .
If  such that , then it is called a total function.

Let  be a total function. If   
          such that , 
then  is called a surjective function.
If  
          implies , then  is called an 
injektive or one-to-one function.
If  is both surjective and injective then it is called bijektive.

Remark 2.2.

The traditional notation for the relation  is , as we are 
used with e.g. the relations   and .

If  and  are two function, then the union of them 
can be defined as the union  of relations. This, however, is not
necessarily a function. If we assume, that , then  is 
a function and .

Since in the following parts we want to prove that the mathematical concept of algorithm we construct can be precisely specified, thus the detailed definition of the alphabet, word and language are necessary. There is a particular need to find place of the empty symbol in the structure.

Definition 2.3.

The finite, non-empty set  is called an alphabet. 
The elements of are called letters (somtemies characters or symbols).
If , then we assume for  that .
(The symbol  is called the empty character.)

Definition 2.4.

Let  be a nonepty set and  let  be a map.

Assume that 
1. ; 
2.  sympols  such that ;
3.  and  implies  if
   and only if  and ;
4.   
             and , 
   such that ; 
5. (Induction) Let  a statement on the elements of . 
   If ,  holds and  implies , 
   then  
             holds, too;
6. If , then  
            .

Then  is called the set of finite words over the alphabet  
and  is called the empty word. 

As it is usual, we will use the notation  and
 .

Remark 2.5.

1. Let . The map  can be viewed as a transformation,
   which extends the word  by the symbol .
2. One can define a natural embedding  between  and ,
   by .
   Thus the elements of  can be regarded as finite sequences
   of elements of .
3. By 6. of Definition 2.4  , which means that  and  
   are different, but they are corresponding to each other in the 
   two sets.
4. By 6. of Definition 2.4 the 3. can be extended to the cases
    Ús .
5. The 5. pf Definition 2.4 means that every word can be created 
   from the empty word by adding symbols to it. 
   Thus, if , where , 
   then we may denote the word by its traditional notation
   .
6. By point 3. the above represenatation is unique.
7. The previous statement can be extended to the empty symbol with
   the property   .

Definition 2.6.

Let  be a function with properties:
1. ;
2. ,  and .
Then  is called the length of the word .

Theorem 2.7.

             the length  is well defined.

Proof

By definition, the length of a word means the number of steps the map applied on the empty word to get . Since number and the order of the extension steps are fixed for the creation of , the length is unique. ✓

Remark 2.8.

If a word is regarded as a finite sequence of symbols, 
then the length is equal to the number of symbols in it. 

Definition 2.9.

Let  be a binary operation on , i.e. ⋅: 
with the properties:
1.  let ;
2.  and  implies .
Then the operation  is called the concatenation.
Traditionally we use the simpler  notation instead 
of  .

The operation of concatenation has the following property.

Theorem 2.10.

 
          if  and , 
then .

Proof

The proof is by induction on .

a.) By definition, if , then , which means that the statement holds.

b.) Assume that for a given for all words if , then the

statement holds.

Let be a word of length . If the is the last letter of , then for some , where .

By the inductive assumption . Applying the definition of the concatenation,

which means that the statement holds for , too.

Form a.) and b.) by induction the theorem follows. ✓

Theorem 2.11.

          with the binary operation of concatenation is a 
monoid (semigroup with a unit element).

Proof

The proof is again by induction.

1. The concatenation is associative:

a.)By definition .

b.) Assume, that for a given for all words , if , then the associativity holds. Let is such that . Then and satisfying and . By the inductive assumption, for all words the equality holds. Hence

,

which means that the statement is true for , too.

From a.) and b.) by induction the associativity follows.

2. is a unit element.

By definition for all .

The equality can be proven by induction.

a.) By the definition .

b.) Assume for all that if , then . Let be a word of length . Then and , such that and . By the inductive assumption

,

which means that the statement holds for , too.

From a.) and b.) by induction follows.

With this, the proof is complete. ✓

Theorem 2.12.

The operation of concatenation satisfies the 
simplification rule, i.e. 
 the eqality  implies . 
Similarly, the equality  implies  .

Proof

As before, the proof can be done by induction. In the firs case the induction is on , while in then second case the induction is on and , simultaneously. ✓

The following definitions are useful for the description of the structure of word.

Definition 2.13.

Let  be such that . 
Then  is called a prefix, while  is called a postfix of .

Remark 2.14.

A word is a so called trivial pre- and postfix
of itself. 
The empty word is a trivial pre- and postfix of
any word.

One may define transformations in the form on the set of finite words. These transformation can have some good properties. Some of the most important ones are given in the following.

Definition 2.15.

A transformation  is called length preserving,
if  the equality  holds.

Remark 2.16.

Length preserving transformation e.g. the mirror image,
permutation of characters, cyclic permutation, e.t.c.

Definition 2.17.

A transformation  is called prefix preserving, 
if  words  , such that .

Remark 2.18.

In the examples of Remark 2.16, the mirror image and
cyclic permutation is not, but the character permutation
is prefix preserving transformation. 
Prefix preserving, but not length preserving, however, 
the following transformation:
. (Repetition.)

Using the concept of words, we arrive to the definition of an important object of the theory of algorithms.

Definition 2.19.

Let  be a finite alphabet. The set  is called a 
(formal) language over .

It is natural idea to define the usual set operations on languages. E.g. if, are two languages, then and are languages, too. The language is called the complement of .

Other important operations on languages are the following.

Definition 2.20.

Let  be two languages. The language 
 is called the concatenation
of the languages and denoted by .

Remark 2.21.

Concatenating  by itself, we may use the 
following simplified notation
 Ús , ha .

Definition 2.22.

Let  be a language. The language  
is called the iteration - or the closure for the
concatenation - of  .

Remark 2.23.

The name closure comes from the fact, that  
is exactly the smallest language, such that 
 is a subset of it and closed under concatenation.

Definition 2.24.

Let  be a class of languages. 
Then the class . 
Here  denites the complement of .

Remark 2.25.

The class  is in general not the complement
of .  Actually  is not necessarily 
empty. 
If e.g.  is the class of all languages,
then .

Theorem 2.26.

Let  and  be two class of languages over the
same alphabet. 
Then  
1. ;
2. ;
3. ;
4.  if and omly if .

Proof

We apply the usual set theoretic proofs for equalities.

1.We may write the following chain of equivalences

or or .

2. Similarly, we may write the following chain of equivalences:

and and .

3. In this case we may write:

.

4. By definition if and only if and if and only if . Again by definition if and only if implies . This, however, stands exactly when implies . ✓