Cryptography Reference
In-Depth Information
Theorem 8.2 (Kleene 1956 [83]).
A language is regular if and only if it is the language
accepted by a finite automaton.
8.1.3
Beyond Finite Automata Capabilities
Finite automata do some computations in very simple ways. The output of the compu-
tation is the information whether the input word is accepted or not. Regular languages
are thus a nice notion of simple computation. It is however not complete because many
simple languages are not regular, thus not accepted by finite automata, as shown by the
following result.
Theorem 8.3.
The set of all
0
i
1
i
words for i
≥
0
is not a regular language.
Proof.
Let
) be a finite automaton which accepts this language, and
let us look for a contradiction. For any
i
,welet
q
i
be
A
=
(
Q
,
q
0
,
F
,δ
δ
(
q
0
,
0
i
). Obviously,
δ
(
q
i
,
1
i
)is
a final state. But since 0
i
1
j
is not accepted for
i
=
j
, all
q
i
must be pairwise different.
Hence we have an infinite sequence of states
q
0
,
q
1
,...
, which is not possible for finite
automata.
Finite automata could have been thought of as a good model for computation since
all computers are indeed finite automata. What the above result shows is that 0
i
1
i
cannot be recognized when
i
is very long, especially when it is much longer than what
the computer can store. Therefore this notion does not scale. Furthermore, the finite
automaton model does not capture the intuitive notion of complexity since the transition
function can be very expensive to implement. This is why we need another model.
8.1.4
Turing Machines
A Turing machine is a simple computer model which formalizes a strong notion of
computability. It is defined by
1. a special
blank
character
B
,
2. an alphabet
which does not include
B
,
3. a finite automaton (
Q
,
q
0
,
F
,δ
) on the alphabet
∪{
B
}
,
4. an extension of
δ
which outputs an element of
∪{
B
}
and an element of
{
,
}
left
right
in addition to the new state.
A Turing machine has a
tape
which is an infinite sequence of
cells
. Each cell contains
an element of
. The Turing machine also has a
tape head
which points on a
given cell. Originally, the state of the machine is the initial state
q
0
, the tape head points
on the leftmost cell, the leftmost cells are filled with characters of the input word, and
all other cells are filled with blank characters. For every move of the machine,
∪{
B
}
1. the machine reads the pointed cell and applies
δ
on it,
2. change the state according to the output of
δ
,
Search WWH ::
Custom Search