Cryptography Reference
In-Depth Information
1
1
1
q
0
q
1
q
2
Figure 8.1.
Finite automaton which recognizes odd unary numbers.
As an example, we define an automaton which accepts 1(11)
∗
with the unary
alphabet
={
1
}
. We take
Q
={
q
0
,
q
1
,
q
2
}
and
F
={
q
1
}
. We define
δ
by
δ
(
q
0
,
1)
=
q
1
δ
(
q
1
,
1)
=
q
2
δ
(
q
2
,
1)
=
q
1
.
Obviously, we reach state
q
1
after an odd number of 1 characters. This automaton
is depicted in Fig. 8.1. Circles represent states. Double circles represent the terminal
states. Transitions are represented by arrows. The arrow with no starting state shows
the initial state.
These automata are called
deterministic
, but we also consider
nondeterminis-
tic
automata for which
δ
is simply a subset of
Q
×
×
Q
(and not a function
of
Q
×
to
Q
). A word
u
=
(
a
1
, ...,
a
) is accepted if there exists a sequence
((
q
0
,
q
i
) starting from
the initial state
q
0
, all along the characters
a
i
of
u
, and ending on a final state
q
∈
a
1
,
q
1
)
, ...,
(
q
−
1
,
a
,
q
)) of
consecutive transitions (
q
i
−
1
,
a
i
,
F
.As
a matter of fact, languages accepted by nondeterministic automata can also be accepted
by deterministic ones as the following theorem shows.
Theorem 8.1.
For any nondeterministic finite automaton
A
, there exists a deterministic
finite automaton
B
which accepts the very same language.
). We let
Q
be the set of all subsets of
Q
and
F
be the
set of all subsets of
Q
which contain at least one element of
F
.Welet
q
0
={
Proof.
Let
A
=
(
Q
,
q
0
,
F
,δ
q
0
}
.We
(
Q
,
q
0
,
F
,δ
) as follows. For any subset
q
define the deterministic automaton
B
=
δ
(
q
,
of
Q
and any character
a
,welet
a
) be the set of all states
r
in
Q
such that there
q
such that (
q
exists at least one state
q
∈
,
a
,
r
)
∈
δ
. We now need to prove that
B
accepts the very same language as
A
.
δ
(
q
0
,
For this we prove by induction (on
) that
a
1
||···||
a
) is exactly the set
of all states
q
∈
Q
such that there exists a sequence (
q
0
,
a
1
,
q
1
)
,...,
(
q
−
1
,
a
,
q
)
: assuming this is true for
q
=
δ
(
q
0
,
of elements of
δ
a
1
···
a
−
1
), we know that
δ
(
q
0
,
a
1
||···||
δ
(
q
,
a
) is equal to
a
), which is the set of all
r
such that there exists
δ
(
q
0
,
∈
q
such that (
q
,
a
,
∈
δ
a
1
||···||
at least one
q
r
)
. Therefore, this holds for
a
)
as well by definition of
q
and
δ
(
q
,
a
).
The following theorem characterizes the languages accepted by some automata.
3
3
The proof is available in Ref. [92, p. 33] or [19, p. 321].
Search WWH ::
Custom Search