Elements of Complexity Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 212

We can manipulate languages by using regular operations :

1. concatenation: AB is the language of all words made from the concatenation
of a word from the language A and a word from the language B 1 ;
2. power: A i

is recursively defined as A i − 1 A with A 0

={ ε } ;

B is simply the union of A and B 2 ;
4. closure: A ∗ is the union of all A i

3. union: A ∪

for i ≥ 0.

∗ : ∗ is the set of all

We notice that languages over the alphabet are subsets of

words over the alphabet .A regular language is a language obtained with the above

operations from elementary languages:

1. the empty language ∅ ,

2. the null language ,

3. all single-character languages

{ ε }

{ a } for a ∈ .

For simplicity, we omit braces in operations on languages so that ε denotes { ε } , and a

denotes . For instance, the set of odd unary numbers is a regular language over the

unary alphabet since it is 1(11) ∗ .

{ a }

8.1.2 Finite Automata

A finite automaton consists of

1. a finite set Q of states ,
2. a particular state q 0 ∈ Q called the initial state ,

3. a particular subset F ⊆ Q of final states ,

4. a finite set called the input alphabet ,

5. a function δ from Q × to Q called the transition function .

δ × ∗ by

We recursively extend the function on Q

δ ( q ,ε ) = q

and

δ ( q , u || a ) = δ ( δ ( q , u ) , a ) .

If a word u is such that δ ( q 0 , u ) ∈ F , we say that u is accepted by the

automaton. The set of all accepted words is the language accepted by the

automaton .

1

This operation is often called multiplication .

2

This operation is often called addition .