Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
194 6. Some Topics on Structure Problem
j is the integer satisfying s
j
= δ
(s
i
,y). Using Lemma 6.1.1 (a), ¯s
≺S, s
i
implies
¯
δ
(¯s
,y) ≺δ
M
(S, y),δ
(s
i
,y), therefore, implies
¯
δ
(¯s
,y) ≺S, s
j
,
that is,
¯
δ
(¯s
,y) ∈
¯
C
j
. It follows that
¯
δ
(
¯
C
i
,y) ⊆
¯
C
j
.Sinceλ(S, X)=Y ,
for any y ∈ Y ,
¯
δ
(S, s
i
,y)and
¯
λ
(S, s
i
,y) are defined. It follows that
¯
δ
(
¯
C
i
,y) = ∅. Noticing S, s
i
∈
¯
C
i
,weobtain
¯
M
∈M(
¯
C
1
,...,
¯
C
h
).
Defining ϕ(¯c
i
)=s
i
, i =1,...,h,using
¯
λ
(S, s
i
,y)=λ
(s
i
,y), it is easy
to verify that ϕ is an isomorphism from
¯
M
to M
. Therefore,
¯
M
and M
are isomorphic.
Let M
= Y,X,{c
1
,...,c
h
},δ
,λ
,whereδ
(c
i
,y)=c
j
for the inte-
ger j satisfying
¯
δ
(¯c
i
,y)=¯c
j
,andλ
(c
i
,y)=
¯
λ
(¯c
i
,y). Since
¯
δ
(¯c
i
,y)=¯c
j
implies
¯
δ
(
¯
C
i
,y) ⊆
¯
C
j
, δ
(c
i
,y)=c
j
implies
¯
δ
(
¯
C
i
,y) ⊆
¯
C
j
. It follows that
δ
(c
i
,y)=c
j
implies
˜
δ(C
i
,y) ⊆ C
j
.Let
˜
t be a root state corresponding to
s
i
.Then
˜
t ∼S, s
i
.FromS, s
i
∈
¯
C
i
,wehave
˜
t ∈ C
i
.Since
¯
δ
(S, s
i
,y)
is defined,
˜
δ(
˜
t, y) is defined. It follows that
˜
δ(C
i
,y) = ∅.From
˜
t ∼S, s
i
,
we have
¯
λ
(S, s
i
,y)=
˜
λ(
˜
t, y). Since
¯
λ
(¯c
i
,y)=
¯
λ
(S, s
i
,y), we have
λ
(c
i
,y)=
¯
λ
(¯c
i
,y)=
˜
λ(
˜
t, y). Thus M
is in M(C
1
,...,C
h
). Clearly, M
and
¯
M
are isomorphic. Thus M
and M
are isomorphic. Therefore, M
and M
are equivalent. We conclude that for any inverse finite automaton
M
with delay τ of M, there exist
˜
M in J (M,M
)andM
in M
0
(
˜
M)such
that M
∼ M
.
if : Suppose that M
∼ M
for some M
∈M
0
(
˜
M), where
˜
M ∈
J (M,M
). Then there exists a closed compatible family C
1
,...,C
h
of
˜
M
such that {C
1
,...,C
h
} = C(
˜
M)andM
∈M(C
1
,...,C
h
). Thus M
=
Y,X,{c
1
,...,c
h
},δ
,λ
,whereδ
(c
i
,y)=c
j
for some j satisfying the
condition ∅ =
˜
δ(C
i
,y) ⊆ C
j
,andλ
(c
i
,y)=
˜
λ(˜s, y), ˜s being the root state
in C
i
. For any state s of M,anystatec
i
of M
,1 i h,andanyx
0
, ...,
x
l
in X,letλ(s, x
0
...x
l
)=y
0
...y
l
and λ
(c
i
,y
0
...y
l
)=z
0
...z
l
.Weprove
z
τ
...z
l
= x
0
...x
l−τ
in case of τ l. Suppose τ l and let ˜s be the root
state in C
i
.Sincey
0
...y
l
∈ R
M
,wehaveδ
M
(S, y
0
...y
l
) = ∅. It follows that
˜
λ(˜s, y
0
...y
l
) is defined. Thus we have
λ
(c
i
,λ(s, x
0
...x
l
)) =
˜
λ(˜s, y
0
...y
l
)
=
˜
λ(˜s, y
0
...y
τ−1
)
˜
λ(
˜
δ(˜s, y
0
...y
τ−1
),y
τ
...y
l
)
=
˜
λ(˜s, y
0
...y
τ−1
)
¯
λ
(δ
M
(S, y
0
...y
τ−1
), y
τ−1
,...,y
0
,y
τ
...y
l
)
=
˜
λ(˜s, y
0
...y
τ−1
)λ
(y
τ−1
,...,y
0
,y
τ
...y
l
)
=
˜
λ(˜s, y
0
...y
τ−1
)x
0
...x
l−τ
.
It follows that z
τ
...z
l
= x
0
...x
l−τ
.ThusM
is an inverse finite automaton
with delay τ of M.SinceM
∼ M
, M
is an inverse with delay τ of M.
6.2 Inverses of a Finite Automaton 195
Joining all trees in T
(Y,X,τ − 1) to the partial finite automaton
¯
M
τ
,
we get a partial finite automaton, denoted by
˜
M
max
. It is easy to see that
˜
M
max
∈J(M,M
).
Theorem 6.2.2. If M = X, Y, S, δ, λ is an invertible finite automaton
with delay τ and λ(S, X)=Y, then a finite automaton M
= Y,X,S
,δ
,λ
is an inverse with delay τ of M if and only if there exist a finite automaton
M
in M
0
(
˜
M
max
) and a finite subautomaton M
of M
such that M
∼
M
.
Proof. if : Suppose that M
∈M
0
(
˜
M
max
)andM
∼ M
for some finite
subautomaton M
of M
.Fromλ(S, X)=Y , M
is a finite automaton.
Since
˜
M
max
∈J(M, M
), from Theorem 6.2.1, M
is an inverse with delay
τ of M. It follows that M
is an inverse with delay τ of M.FromM
∼
M
, M
is an inverse with delay τ of M.
only if : Suppose that M
is an inverse with delay τ of M.FromTheo-
rem 6.2.1, there exist
˜
M in J (M,M
)andM
in M
0
(
˜
M) such that M
∼
M
. Clearly,
˜
M is a partial finite subautomaton of
˜
M
max
and any root state
of
˜
M is a root state of
˜
M
max
.LetM
= Y, X, {c
1
,...,c
h
},δ
,λ
∈
M(C
1
,...,C
h
) for some closed compatible family C
1
,...,C
h
of
˜
M with
{C
1
,...,C
h
} = C(
˜
M). Let
˜
t
i
be the root state in C
i
, i =1,...,h.Itiseasy
to prove that there exists a closed compatible family C
1
,...,C
h
of
˜
M
max
with {C
1
,...,C
h
} = C(
˜
M
max
) such that h h
and
˜
t
i
is the root state in
C
i
for any i,1 i h. Clearly, C
i
= {˜s | ˜s is a state of
˜
M,˜s ≺
˜
t
i
} and
C
i
= {˜s | ˜s is a state of
˜
M
max
, ˜s ≺
˜
t
i
}, i =1,...,h.Since
˜
M is a partial
finite subautomaton of
˜
M
max
,wehaveC
i
⊆ C
i
, i =1,...,h. And for any
y ∈ Y ,
˜
δ(C
i
,y) ⊆ C
j
implies
˜
δ
max
(
˜
t
i
,y)=
˜
δ(
˜
t
i
,y) ∈ C
j
⊆ C
j
, therefore, us-
ing Lemma 6.1.1 (a),
˜
δ(C
i
,y) ⊆ C
j
implies
˜
δ
max
(C
i
,y) ⊆ C
j
, i, j =1,...,h,
where
˜
δ and
˜
δ
max
are the next functions of
˜
M and
˜
M
max
, respectively. Thus we
can construct M
= Y,X,{c
1
,...,c
h
},δ
,λ
in M(C
1
,...,C
h
)such
that M
is a finite subautomaton of M
. Clearly, M
∈M
0
(
˜
M
max
). This
completes the proof of the theorem.
Noticing that the condition “there exist a finite automaton M
in
M
0
(
˜
M
max
) and a finite subautomaton M
of M
such that M
∼ M
”
is equivalent to the condition “there exists a finite automaton M
in
M
0
(
˜
M
max
) such that M
≺ M
”, the theorem can be restated as the
following corollary.
Corollary 6.2.1. If M = X, Y, S, δ, λ is an invertible finite automaton
with delay τ and λ(S, X)=Y , then a finite automaton M
= Y,X,S
,δ
,λ
is an inverse with delay τ of M if and only if there exists a finite automaton
M
in M
0
(
˜
M
max
) such that M
≺ M
.
196 6. Some Topics on Structure Problem
We deal with the case |X| = |Y |. In this case, from Theorem 1.4.6, since
M is invertible with delay τ,wehaveR
M
= Y
∗
. Thus we can construct
a finite automaton recognizer M
out
= Y,{S},δ
M
,S,{S} to recognize R
M
,
where δ
M
(S, y)=S for any y in Y .Itiseasytoseethatboth
¯
M
and
¯
M
τ
are finite automata. Therefore, the partial finite automaton
˜
M
max
is a
finite automaton. Using Lemma 6.1.2, it follows that each finite automaton in
M
0
(
˜
M
max
) is equivalent to
˜
M
max
. Therefore, finite automata in M
0
(
˜
M
max
)
are equivalent to each other. From Corollary 6.2.1, we obtain the following
corollary.
Corollary 6.2.2. If M = X, Y, S, δ, λ is an invertible finite automaton
with delay τ and |X| = |Y |, then a finite automaton M
= Y,X,S
,δ
,λ
is an inverse with delay τ of M if and only if M
≺ M
,whereM
is any
finite automaton in M
0
(
˜
M
max
) or M
=
˜
M
max
.
Corollary 6.2.2 means that in the case of |X| = |Y |, the finite automaton
˜
M
max
and each finite automaton in M
0
(
˜
M
max
) are a “universal” inverse with
delay τ of M. And in the general case of |X| |Y |, Theorem 6.2.2 means
that all finite automata in the set M
0
(
˜
M
max
), not one finite automaton in it,
constitute the “universal” inverses with delay τ of M. But a nondeterministic
finite automaton can be constructed as follows, which is a “universal” inverse
with delay τ of the finite automaton M.
From
˜
M
max
= Y,X,
˜
S,
˜
δ,
˜
λ, we construct a nondeterministic finite au-
tomaton M
= Y,X,C(
˜
M
max
),δ
,λ
as follows. For any T in C(
˜
M
max
)
and any y in Y , define δ
(T,y)={W | W ∈ C(
˜
M
max
),
˜
δ(T,y) ⊆ W } and
λ
(T,y)={
˜
λ(˜s, y)},where˜s is the root state of
˜
M
max
in T .
Theorem 6.2.3. The nondeterministic finite automaton M
is an inverse
with delay τ of the finite automaton M.
Proof.LetC
0
be a state of M
,ands a state of M.WeprovethatC
0
τ-matches s. That is, for any l τ,anyx
0
,x
1
,...,x
l
,z
0
,z
1
,...,z
l
in X
and any y
0
,y
1
,...,y
l
in Y , y
0
y
1
... y
l
= λ(s, x
0
x
1
...x
l
)andz
0
z
1
...z
l
∈
λ
(C
0
,y
0
y
1
...y
l
)implyz
τ
z
τ+1
...z
l
= x
0
x
1
...x
l−τ
. Suppose y
0
y
1
...y
l
=
λ(s, x
0
x
1
...x
l
)andz
0
z
1
...z
l
∈ λ
(C
0
,y
0
y
1
...y
l
), where l τ , x
0
,x
1
,...,
x
l
, z
0
,z
1
,...,z
l
∈ X,andy
0
,y
1
,...,y
l
∈ Y .Weprovez
τ
z
τ+1
...z
l
=
x
0
x
1
...x
l−τ
. From the definition of λ
, there exist states C
1
,...,C
l
of M
such that C
j+1
∈ δ
(C
j
,y
j
) holds for j =0, 1,...,l− 1andz
j
∈ λ
(C
j
,y
j
)
holds for j =0, 1,...,l. From the construction of M
, it follows that
˜
δ(C
j
,y
j
) ⊆ C
j+1
holds for j =0, 1,...,l − 1andz
j
=
˜
λ(
˜
t
j
,y
j
)holds
for j =0, 1,...,l,where
˜
t
j
is the root state of
˜
M in C
j
, j =0, 1,...,l.
Let ˜s
0
=
˜
t
0
.Sincey
0
...y
l
∈ R
M
, we can recursively define ˜s
j+1
=
˜
δ(˜s
j
,y
j
), j =0, 1,...,l − 1. Since y
0
...y
l
∈ R
M
,
˜
λ(˜s
j
,y
j
) is defined,
6.2 Inverses of a Finite Automaton 197
j =0, 1,...,l.From˜s
0
∈ C
0
and
˜
δ(C
j
,y
j
) ⊆ C
j+1
, j =0, 1,...,l − 1,
we have ˜s
j
∈ C
j
, j =1,...,l. It follows that ˜s
j
≺
˜
t
j
, j =1,...,l.Thus
z
j
=
˜
λ(
˜
t
j
,y
j
)=
˜
λ(˜s
j
,y
j
), j =0, 1,...,l. From the construction of
˜
M
max
,
˜
λ(˜s
j
,y
j
)=λ
(y
j−1
,...,y
j−τ
,y
j
), j = τ,...,l.SinceM
is an inverse of M
and y
0
y
1
...y
l
= λ(s, x
0
x
1
...x
l
), we have λ
(y
j−1
,...,y
j−τ
,y
j
)=x
j−τ
,
j = τ,...,l. It follows that z
j
=
˜
λ(˜s
j
,y
j
)=λ
(y
j−1
,...,y
j−τ
,y
j
)=x
j−τ
,
j = τ,...,l.Thatis,z
τ
z
τ+1
...z
l
= x
0
x
1
...x
l−τ
. We conclude that C
0
τ-matches s. Therefore, M
is an inverse with delay τ of M.
Theorem 6.2.4. If M = X, Y, S, δ, λ is an invertible finite automaton
with delay τ and λ(S, X)=Y, then a finite automaton M
= Y,X,S
,δ
,λ
is an inverse with delay τ of M if and only if M
≺ M
.
Proof. only if : Suppose that M
is an inverse finite automaton with
delay τ of M. From Corollary 6.2.1, there exist a closed compatible family
C
1
,...,C
h
of
˜
M
max
and a finite automaton
¯
M
= Y,X,{c
1
,...,c
h
},
¯
δ
,
¯
λ
in M(C
1
,...,C
h
) such that M
≺
¯
M
and {C
1
,...,C
h
} = C(
˜
M
max
), where
¯
δ
(c
i
,y)=
c
j
, if
˜
δ(C
i
,x) = ∅,
undefined, if
˜
δ(C
i
,x)=∅,
¯
λ
(c
i
,y)=
˜
λ(s, y), if ∃s
1
(s
1
∈ C
i
&
˜
λ(s
1
,y) is defined),
undefined, otherwise,
i =1,...,h, y ∈ Y,
j is an arbitrary integer satisfying
˜
δ(C
i
,y) ⊆ C
j
,ands is an arbitrary state
in C
i
such that
˜
λ(s, y) is defined.
We prove that
¯
M
≺ M
. For any i,1 i h, c
i
and C
i
are states of
¯
M
and M
, respectively. We prove c
i
≺ C
i
. For any y
0
,y
1
,...,y
l
∈ Y ,let
¯
λ
(c
i
,y
0
y
1
...y
l
)=x
0
x
1
...x
l
,wherex
0
,x
1
,...,x
l
∈ X. Then there exist
states c
i
j
,j =0, 1,...,l of
¯
M
such that c
i
0
= c
i
,and
c
i
j+1
=
¯
δ
(c
i
j
,y
j
),j=0, 1,...l− 1,
x
j
=
¯
λ
(c
i
j
,y
j
),j=0, 1,...l.
Thus we have
˜
δ(C
i
j
,y
j
) ⊆ C
i
j+1
, j =0, 1,...,l − 1. It follows that C
i
j+1
∈ δ
(C
i
j
,y
j
), j =0, 1,...,l − 1. From the definitions of
¯
λ
and λ
,we
have {
¯
λ
(c
i
j
,y
j
)} = {
˜
λ(t
j
,y
j
)} = λ
(C
i
j
,x
j
), therefore, λ
(C
i
j
,y
j
)={x
j
},
j =0, 1,...,l,wheret
j
is the root state of
˜
M in C
j
. This yields x
0
x
1
...
x
l
∈ λ
(C
i
, y
0
y
1
...y
l
). We conclude that c
i
≺ C
i
.
For any state s
of M
,fromM
≺
¯
M
, there exists a state c
i
of
¯
M
such that s
≺ c
i
.Usingc
i
≺ C
i
,itiseasytoverifythats
≺ C
i
. We conclude
M
≺ M
.
198 6. Some Topics on Structure Problem
if : Suppose that M
≺ M
. For any state s
of M
,wecanchoosea
state s
of M
such that s
≺ s
. For any state s of M, from Theorem 6.2.3,
s
τ-matches s.Usings
≺ s
,itiseasytoverifythats
τ-matches s.Thus
M
is an inverse with delay τ of M.
6.3 Original Inverses of a Finite Automaton
Given an inverse finite automaton M
= Y,X,S
,δ
,λ
with delay τ,let
f(y
τ
,...,y
0
)=
λ
(δ
(s
,y
0
...y
τ−1
),y
τ
), if |λ
(δ
(S
,y
0
...y
τ−1
),y
τ
)| =1,
undefined, otherwise,
y
0
,...,y
τ
∈ Y,
where s
is an arbitrarily fixed element in S
. We construct a labelled tree
with level τ . Each vertex with level i,0 i τ,emits|X| arcs. Each arc
has a label of the form (x, y), where x ∈ X and y ∈ Y . x and y are called
the input label and the output label, respectively. The input labels of |X| arcs
emitted from the same vertex are different letters in X. If the labels of arcs
in a path from the root of length τ +1 are (x
0
,y
0
), (x
1
,y
1
), ...,(x
τ
,y
τ
), then
f(y
τ
,...,y
0
)=x
0
holds. We use
¯
T to denote the set of all such trees.
We use M(M
) to denote the set of all M (T ,ν,δ), T ranging over all
nonempty closed subset of
¯
T . (For the construction of the finite automaton
M(T ,ν,δ), see Sect. 1.6 of Chap. 1.)
Lemma 6.3.1. If M
= Y,X,S
,δ
,λ
is an inverse finite automaton with
delay τ,thenM
is an inverse of any finite automaton in M(M
).
Proof.LetM (T ,ν,δ) be a finite automaton in M(M
). Denote M(T ,ν,δ)
= X, Y , S, δ, λ. For any s in S and any x
i
in X, i =0, 1,...,τ,let
y
0
y
1
...y
τ
= λ(s, x
0
x
1
...x
τ
), where y
i
∈ Y , i =0, 1,...,τ. From the con-
struction of M(T ,ν,δ), it is easy to show that if s = T,j,whereT ∈T,
then y
0
y
1
...y
τ
is the output label of a path from the root of T of length
τ + 1 with input label x
0
x
1
...x
τ
. Therefore, f(y
τ
,...,y
0
)=x
0
holds. From
the definition of f, for any s
in S
,wehaveλ
(δ
(s
,y
0
y
1
...y
τ−1
),y
τ
)=
f(y
τ
,...,y
0
). It follows that
λ
(s
,λ(s, x
0
x
1
...x
τ
)) = λ
(s
,y
0
y
1
...y
τ
)
= λ
(s
,y
0
y
1
...y
τ−1
)λ
(δ
(s
,y
0
y
1
...y
τ−1
),y
τ
)
= λ
(s
,y
0
y
1
...y
τ−1
)f(y
τ
,...,y
0
)
= λ
(s
,y
0
y
1
...y
τ−1
)x
0
.
We conclude that M
is an inverse of M(T ,ν,δ)withdelayτ.
6.3 Original Inverses of a Finite Automaton 199
We use T
m
to denote the maximum closed subset of
¯
T . Notice that T
m
is
unique. We use
¯
M(M
) to denote the set of all M(T
m
,ν,δ).
Lemma 6.3.2. If M
= Y,X,S
,δ
,λ
is an inverse finite automaton with
delay τ of M = X, Y, S, δ, λ,thenthereexistsM
2
in
¯
M(M
) such that M
and some finite subautomaton of M
2
are isomorphic.
Proof. We construct M(T
1
,ν
1
,δ
1
) as follows. Partition S so that s
1
and s
2
belong to the same block if and only if T
M
τ
(s
1
)=T
M
τ
(s
2
). (For the definition
of T
M
τ
(s), see Sect. 1.6 of Chap. 1.) We use C
1
, ..., C
r
to denote such blocks.
In the case of s ∈ C
j
, we take ν
1
(T
M
τ
(s)) = |C
j
|. Take T
1
= {T
M
τ
(s) | s ∈ S}
and S
1
= {T,j|T ∈T
1
,j =1,...,ν
1
(T )}.
Fix a one-to-one mapping ϕ from S onto S
1
such that ϕ(s)=T
M
τ
(s),j
for some j. From the definition of ν
1
,suchaϕ is existent. Define δ
1
(ϕ(s),x)=
ϕ(δ(s, x)). It is easy to verify that M(T
1
,ν
1
,δ
1
) is a finite automaton and ϕ
is an isomorphism from M to M (T
1
,ν
1
,δ
1
). Therefore, M and M (T
1
,ν
1
,δ
1
)
are isomorphic.
For any s in S and any x
0
, ..., x
τ
in X,lety
0
...y
τ
= λ(s, x
0
...x
τ
),
where y
0
, ..., y
τ
∈ Y .SinceM
is an inverse finite automaton with delay
τ of M, for any s
in S
,wehaveλ
(δ
(s
,y
0
...y
τ−1
),y
τ
)=x
0
. It follows
that f(y
τ
,...,y
0
)=x
0
.ThusT
M
τ
(s)isin
¯
T . This yields T
1
⊆
¯
T .SinceT
1
is
closed, we have T
1
⊆T
m
.Let
ν
2
(T )=
ν
1
(T ), if T ∈T
1
,
1, if T ∈T
m
\T
1
,
δ
2
(T,i,x)=
δ
1
(T,i,x), if T ∈T
1
,
¯
T,1, if T ∈T
m
\T
1
,
where
¯
T is an arbitrarily fixed x-successor of T in T
m
.ThenM(T
m
,ν
2
,δ
2
) ∈
¯
M(M
). Choose M(T
m
,ν
2
,δ
2
)asM
2
. Clearly, M(T
1
,ν
1
,δ
1
) is a finite sub-
automaton of M
2
.
From the proof of the above lemma, we have the following corollary.
Corollary 6.3.1. If M
= Y,X,S
,δ
,λ
is an inverse finite automaton
with delay τ of M = X, Y, S, δ, λ, then there exists M
1
in M(M
) such that
M and M
1
are isomorphic.
From Lemmas 6.3.1 and 6.3.2, we obtain the following theorem.
Theorem 6.3.1. M
is an inverse finite automaton with delay τ of a finite
automaton M if and only if there exist M
2
in
¯
M(M
) and a finite subau-
tomaton M
1
of M
2
such that M and M
1
are isomorphic.
200 6. Some Topics on Structure Problem
Similarly, from Lemma 6.3.1 and Corollary 6.3.1, we obtain the following
theorem.
Theorem 6.3.2. M
is an inverse finite automaton with delay τ of a finite
automaton M if and only if there exists M
1
in M(M
) such that M and M
1
are isomorphic.
Let M(T
m
)=X, Y, T
m
,δ,λ be a nondeterministic finite automaton,
where
δ(T,x)={
¯
T |
¯
T ∈T
m
,
¯
T is an x-successor of T },
λ(T,x)={y},
T ∈T
m
,x∈ X,
and (x, y) is the label of an arc emitted from the root of T . Notice that δ(T,x)
and λ(T,x) are nonempty.
Theorem 6.3.3. (a) M
is an inverse finite automaton with delay τ of the
nondeterministic finite automaton M(T
m
).
(b) If M
is an inverse finite automaton with delay τ of a finite automaton
M, then M ≺ M (T
m
).
Proof. (a) For any state T
0
of M(T
m
)andanyx
0
,x
1
,...,x
l
in X,let
y
0
y
1
...y
l
∈ λ(T
0
, x
0
x
1
...x
l
), where l τ ,andy
0
,y
1
,... ∈ Y . Then there
exist states T
1
,T
2
,...,T
l+1
of M(T
m
) such that T
i+1
∈ δ(T
i
,x
i
)andy
i
∈
λ(T
i
,x
i
) hold for i =0, 1,...,l. From the definition of δ,itiseasytosee
that for any i,0 i l − τ ,(x
i
,y
i
), (x
i+1
,y
i+1
),...,(x
i+τ
,y
i+τ
) are labels
of arcs in a path from the root to a leaf of T
i
. This yields f(y
i+τ
,...,y
i
)=
x
i
, i =0, 1,...,l− τ. It follows that λ
(δ
(s
,y
i
...y
i+τ−1
),y
i+τ
)=x
i
holds
for any state s
of M
. Thus for any state s
0
of M
, λ
(s
0
,y
0
y
1
...y
l
)=
x
0
...x
τ−1
x
0
x
1
...x
l−τ
holds for some x
0
,...,x
τ−1
in X. Therefore, M
is
an inverse finite automaton with delay τ of M(T
m
).
(b) Suppose that M
is an inverse finite automaton with delay τ of a
finite automaton M . From Lemma 6.3.2, there exist M
2
= M(T
m
,ν,δ
2
)
and a finite subautomaton M
1
of M
2
such that M and M
1
are isomor-
phic. We prove M
2
≺ M (T
m
). For any state T
0
,j
0
of M
2
, T
0
is a state
of M(T
m
). To prove T
0
,j
0
≺T
0
,letx
0
,x
1
,...,x
l
be in X,andy
0
y
1
...y
l
=
λ
2
(T
0
,j
0
,x
0
x
1
...x
l
), where y
0
,y
1
,...,y
l
are in Y ,andλ
2
is the output
function of M
2
. Thus there exist states T
i
,j
i
, i =1,...,l+1 of M
2
such that
δ
2
(T
i
,j
i
,x
i
)=T
i+1
,j
i+1
and λ
2
(T
i
,j
i
,x
i
)=y
i
, i =0, 1,...,l,whereδ
2
is the next state function of M
2
. From the definition of M (T
m
,ν,δ
2
), T
i+1
is
an x
i
-successor of T
i
and (x
i
,y
i
) is the label of an arc emitted from the root
of T
i
. From the definition of M(T
m
), we have y
0
y
1
...y
l
∈ λ(T
0
,x
0
x
1
...x
l
).
6.4 Weak Inverses of a Finite Automaton 201
Thus T
0
,j
0
≺T
0
. We conclude that M
2
≺ M(T
m
). Since M
1
is a finite
subautomaton of M
2
, this yields M
1
≺ M(T
m
). Since M is isomorphic to
M
1
,wehaveM ≺ M(T
m
).
Theorem 6.3.3 means that M(T
m
) is a “universal” nondeterministic finite
automaton for finite automata of which M
is an inverse with delay τ .
6.4 Weak Inverses of a Finite Automaton
Given a weakly invertible finite automaton M = X, Y, S, δ,λ with delay τ,
there exists a weak inverse finite automaton with delay τ of M .LetM
=
Y,X,S
,δ
,λ
be a weak inverse finite automaton with delay τ of M.For
each s in S, we choose a state of M
,sayϕ(s), such that ϕ(s) τ-matches s.
For any s in S,letM
s
= Y,2
S
,δ
M
, {s},S
s
\{∅} be a finite automaton
recognizer, where S
s
= {δ
M
({s},β) | β ∈ Y
∗
}, δ
M
is defined in the beginning
of Sect. 6.2. Let R
s
= {λ(s, α) | α ∈ X
∗
}.ItiseasytoverifythatM
s
recognizes R
s
.
We construct a partial finite automaton M
0
= Y,X,S
0
,δ
0
,λ
0
from M
and M as follows. Let
S
0
= T
τ
∪ T
0
,
where
T
0
=
s∈S
T
0
s
,
T
τ
=
s∈S
T
τ
s
,
T
0
s
= {s, β|β ∈ R
s
, |β| <τ},
T
τ
s
= {δ
M
({s},β),δ
(ϕ(s),β)|β ∈ R
s
, |β| τ }.
For any t, s
in T
τ
and any y in Y ,let
δ
0
(t, s
,y)=
δ
M
(t, y),δ
(s
,y), if δ
M
(t, y),δ
(s
,y)∈T
τ
,
undefined, otherwise,
λ
0
(t, s
,y)=
λ
(s
,y), if δ
M
(t, y),δ
(s
,y)∈T
τ
,
undefined, otherwise.
For any s, β in T
0
s
, |β| <τ− 1andanyy in Y ,let
δ
0
(s, β,y)=
s, βy, if s, βy∈T
0
s
,
undefined, otherwise,
λ
0
(s, β,y) = undefined.
202 6. Some Topics on Structure Problem
For any s, β in T
0
s
, |β| = τ − 1andanyy in Y ,let
δ
0
(s, β,y)
=
δ
M
({s},βy),δ
(ϕ(s),βy), if δ
M
({s},βy),δ
(ϕ(s),βy)∈T
τ
s
,
undefined, otherwise,
λ
0
(s, β,y) = undefined.
From the construction of M
0
, for any β ∈ Y
∗
with |β| <τ, δ
0
(s, ε,β)=
s, β if β ∈ R
s
, δ
0
(s, ε,β) is undefined otherwise. For any β ∈ Y
∗
with
|β| = τ, δ
0
(s, ε,β)=δ
M
({s},β),δ
(ϕ(s),β) if β ∈ R
s
, δ
0
(s, ε,β)
is undefined otherwise. For any β ∈ Y
∗
with |β| >τ, δ
0
(s, ε,β)=
δ
0
(δ
M
({s},β
),δ
(ϕ(s),β
),β
)=δ
M
({s},β),δ
(ϕ(s),β) if β ∈ R
s
, δ
0
(s, ε,
β) is undefined otherwise, where β = β
β
with |β
| = τ. Therefore,
δ
0
(s, ε,β) is defined if and only if β ∈ R
s
.
Lemma 6.4.1. If M
is a weak inverse finite automaton with delay τ of M,
then the partial finite automaton M
0
is a weak inverse with delay τ of M.
Proof. Suppose that M
is a weak inverse finite automaton with delay τ
of M. In the construction of M
0
, for any s in S, we choose a state ϕ(s)of
M
such that ϕ(s) τ-matches s.Letα = x
0
x
1
...,wherex
i
∈ X, i =0, 1,...
Then we have
λ
(ϕ(s),λ(s, α)) = x
−τ
...x
−1
x
0
x
1
...,
for some x
−τ
,..., x
−1
in X. Denote λ(s, α)=β
1
β, |β
1
| = τ.Thenβ
1
and any
prefix of β
1
β are in R
s
. It follows that for any prefix β
of β
1
β, δ
0
(s, ε,β
)is
defined. From the construction of M
0
, this yields that for any prefix β
of β,
λ
0
(δ
0
(s, ε,β
1
),β
), i.e., λ
0
(δ
M
({s},β
1
),δ
(ϕ(s),β
1
),β
), is defined and it
equals λ
(δ
(ϕ(s),β
1
),β
). Thus λ
0
(δ
M
({s},β
1
),δ
(ϕ(s),β
1
),β) is defined
and it equals λ
(δ
(ϕ(s),β
1
),β). It follows that
λ
0
(s, ε,λ(s, α)) = λ
0
(s, ε,β
1
β)
= λ
0
(s, ε,β
1
)λ
0
(δ
0
(s, ε,β
1
),β)
= λ
0
(s, ε,β
1
)λ
0
(δ
M
({s},β
1
),δ
(ϕ(s),β
1
),β)
= x
−τ
...x
−1
λ
(δ
(ϕ(s),β
1
),β)
= x
−τ
...x
−1
x
0
x
1
...,
where x
−τ
= ···= x
−1
= . Therefore, s, ε τ -matches s. It follows that
M
0
is a weak inverse with delay τ of M.
Lemma 6.4.2. Let M
be a weak inverse finite automaton with delay τ of
M. For any partial finite automaton M
= Y,X,S
,δ
,λ
, M
is a weak
inverse with delay τ of M if and only if M
0
≺ M
.
6.4 Weak Inverses of a Finite Automaton 203
Proof. only if : Suppose that M
is a weak inverse with delay τ of M.
Given any s in S and any s
0
in T
τ
s
∪ T
0
s
, from the definitions of δ
0
and S
0
,
there exists
¯
β in R
s
such that s
0
= δ
0
(s, ε,
¯
β). Since M
is a weak inverse
with delay τ of M, there exists s
in S
such that s
τ-matches s.Weprove
that δ
(s
,
¯
β) is defined. From the definition of R
s
, there exists β in Y
∗
such
that β = ε,
¯
ββ ∈ R
s
and |
¯
ββ| >τ. It follows that
¯
ββ = λ(s, α)forsomeα of
length |
¯
ββ| in X
∗
. Denote α = x
0
x
1
... x
n
,wherex
0
, x
1
, ..., x
n
∈ X,and
n = |
¯
ββ|−1. Since s
τ-matches s,wehave
λ
(s
,
¯
ββ)=λ
(s
,λ(s, α)) = x
−τ
...x
−1
x
0
...x
n−τ
,
for some x
−τ
, ..., x
−1
in X ∪{ }.Fromβ = ε and x
n−τ
∈ X, it follows that
δ
(s
,
¯
β) is defined.
Let s
0
= δ
(s
,
¯
β). We prove s
0
≺ s
0
. Assume that β in Y
∗
is applicable
to s
0
. In the case of β = ε, it is obvious that β is applicable to s
0
and
λ
0
(s
0
,β) ≺ λ
(s
0
,β). In the case of β = ε,letβ = β
1
y,wherey ∈ Y .Sinceβ
is applicable to s
0
, δ
0
(s
0
,β
1
), i.e., δ
0
(s, ε,
¯
ββ
1
) is defined. Thus
¯
ββ
1
∈ R
s
.It
immediately follows that λ(s, x
0
x
1
...x
n−1
)=
¯
ββ
1
for some x
0
, x
1
, ..., x
n−1
in X,wheren = |
¯
ββ
1
|.Letr =max(τ,n). Take arbitrarily x
n
, x
n+1
,..., x
r
in X.Letλ(s, x
0
x
1
...x
r
)=
¯
ββ
1
β
2
y
r
,forsomeβ
2
in Y
∗
and y
r
in Y .Since
s
τ-matches s,wehave
λ
(s
,
¯
ββ
1
β
2
y
r
)=λ
(s
,λ(s, x
0
x
1
...x
r
)) = x
−τ
...x
−1
x
0
...x
r−τ
,
for some x
−τ
, ..., x
−1
in X ∪{}.Sincer τ,wehavex
r−τ
∈ X.It
follows that δ
(s
,
¯
ββ
1
β
2
) is defined. From δ
(s
,
¯
ββ
1
β
2
)=δ
(s
0
,β
1
β
2
)=
δ
(δ
(s
0
,β
1
),β
2
), δ
(s
0
,β
1
) is defined. Therefore, β is applicable to s
0
.
We have proven that λ(s, x
0
x
1
...x
n−1
)=
¯
ββ
1
and λ
(s
,
¯
ββ
1
β
2
y
r
)=
x
−τ
...x
−1
x
0
...x
r−τ
.Fromr n,wehaveλ
(s
,
¯
ββ
1
)=x
−τ
... x
−1
x
0
... x
n−τ−1
. It follows that λ
(s
,
¯
ββ)=x
−τ
... x
−1
x
0
... x
n−τ−1
¯x
n−τ
,
for some ¯x
n−τ
in X ∪{
}. From the proof of Lemma 6.4.1, s, ε τ-matches
s.Whenλ
0
(δ
0
(s
0
,β
1
),y) is undefined, we have
λ
0
(s, ε,
¯
ββ)=λ
0
(s, ε,
¯
ββ
1
)λ
0
(δ
0
(s, ε,
¯
ββ
1
),y)
= x
−τ
...x
−1
x
0
...x
n−τ−1
x
n−τ
,
where x
−τ
= ··· = x
−1
= x
n−τ
= .Sincex
i
≺ x
i
, i = −τ,...,−1, and x
n−τ
≺ ¯x
n−τ
,wehaveλ
0
(s, ε,
¯
ββ) ≺ λ
(s
,
¯
ββ). This yields that λ
0
(s
0
,β)=
λ
0
(δ
0
(s, ε,
¯
β),β) ≺ λ
(δ
(s
,
¯
β),β)=λ
(s
0
,β). When λ
0
(δ
0
(s
0
,β
1
),y)is
defined, from the construction of M
0
, δ
0
(δ
0
(s
0
,β
1
),y), i.e., δ
0
(s, ε,
¯
ββ), is
defined. It follows that
¯
ββ ∈ R
s
.Thusλ(s, x
0
x
1
...x
n
)=
¯
ββ for some x
0
,
x
1
, ..., x
n
in X.Sinces, ε τ-matches s,wehave
λ
0
(s, ε,
¯
ββ)=λ
0
(s, ε,λ(s, x
0
x
1
...x
n
)) = x
−τ
...x
−1
x
0
...x
n−τ
,