Tao R. Finite Automata and Application to Cryptography

Подождите немного. Документ загружается.

5.4 Two Step Delay 173

Inthecaseofh

−2

,...,x

−c

) = 0, from (5.3) in the condition (c),

λ(s, x

)=f(x

,...,x

−c

)=f



−1

,...,x

−c

) ⊕ x

for any x

∈ X,

where f



−1

,..., x

−c

, s

)=f

−1

,...,x

−c

)orf

−2

,...,x

−c

) ⊕

−1

⊕ x

−1

−2

,..., x

−c+1

, δ

)). It follows that s is a 0-step state.

Inthecaseofh

−2

,...,x

−c

) = 1, from (5.2) in the condition (c),

−2

,..., x

−c+1

, δ

)) = 0 holds; and from (5.3) in the condition (c),

we have λ(s, 0) = λ(s, 1). We further consider h

−1

,...,x

−c+1

,δ

)) and

−1

, ..., x

−c+2

, δ

)). In the subcase of h

−1

,...,x

−c+1

,δ

)) =

1, from (5.3) in the condition (c), h

−1

,...,x

−c+1

,δ

)) = 1 &

−2

,...,x

−c+1

,δ

)) = 0 yields λ(s

, 0) = λ(s

, 1) = λ(s

, 0) =

λ(s

, 1). Thus s is a 1-step state. In the subcase of h

−1

, ..., x

−c+1

)) = 0 & h

−1

, ..., x

−c+2

, δ

)) = 1, from (5.2) in the condi-

tion (c), h

−1

,..., x

−c+1

, δ

)) = 0 yields h

, ..., x

−c+2

, δ

)) = 1

for any x

∈ X. From (5.3) in the condition (c), h

, ..., x

−c+2

, δ

))

=1 & h

−1

,...,x

−c+2

,δ

)) = 1 yields λ(s

, 0) = λ(s

, 1) =

λ(s

, 0) = λ(s

, 1) for any x

∈ X and λ(s

0,0

, 0) = λ(s

1,0

, 0). Thus s is a

 2-step state. It follows that s is a 2-step or 1-step state. In the subcase of

−1

,...,x

−c+1

,δ

)) = 0 & h

−1

,...,x

−c+2

,δ

)) = 0, from (5.3)

in the condition (c), λ(s

, 0) = λ(s

, 1) for i =0, 1. From (5.2) in the condi-

tion (c), h

−1

,...,x

−c+1

, δ

)) = 0 yields h

,...,x

−c+2

,δ

)) =

1 for any x

∈ X. For any x

∈ X,sinceh

,...,x

−c+2

,δ

)) =

1&h

−1

,...,x

−c+2

,δ

)) = 0, from (5.3) in the condition (c), we

have λ(s

, 0) = λ(s

, 1) = λ(s

, 0) = λ(s

, 1) and λ(s

, 0) =

−1

,...,x

−c+2

,δ

)). Since h

−1

,...,x

−c+1

, δ

)) = 0 &

−1

,...,x

−c+2

,δ

)) = 0, from (5.3) and (5.4) in the condition (c),

we have λ(s

, 0) = f

−1

,...,x

−c+1

,δ

)) and

λ(s

, 0) = f

−1

,...,x

−c+1

,δ

)) ⊕ 1 ⊕ h

−1

,...,x

−c+2

,δ

))

= f

−1

,...,x

−c+1

,δ

)) ⊕ 1 ⊕ f

(0,x

−1

,...,x

−c+2

,δ

))

⊕ f

(1,x

−1

,...,x

−c+2

,δ

)).

It follows that λ(s

, 0) = λ(s

, 0) if and only if f

(0,x

−1

,...,x

−c+2

, δ

)) =

(1,x

−1

,...,x

−c+2

,δ

)). Since λ(s

, 0) = f

−1

, ...,x

−c+2

,δ

))

for x

=0, 1, λ(s

, 0) = λ(s

, 0) if and only if λ(s

0,0

, 0) = λ(s

1,0

, 0). Noticing

that λ(s, 0) = λ(s, 1), λ(s

, 0) = λ(s

, 1) and λ(s

, 0) = λ(s

, 1) =

λ(s

, 0) = λ(s

, 1) for x

=0, 1, thus s is a 2-step state.

To sum up, if the condition (c) holds, then any state s of M is a t-step

state for some t,0 t  2. Thus M is weakly invertible with delay 2. 

Theorem 5.4.2. Let M = X, Y, S, δ, λ be a c-order semi-input-memory

ﬁnite automaton SIM(M

,f),andM

= Y

,δ

,λ

 be strongly cyclic.

Let c  2 and X = Y = {0, 1}.ThenM is a feedforward inverse with delay

2 if and only if one of the following conditions holds:

174 5. Structure of Feedforward Inverses

(a) There exists a single-valued mapping f

from X

× S

to Y such that

f(x

,...,x

−c

)=f

−1

,...,x

−c

) ⊕ x

(b) There exists a single-valued mapping f

from X

c−2

× S

to Y such

that

f(x

,...,x

−c

)=f

−3

,...,x

−c

) ⊕ x

−2

from X

c−1

× S

to {0, 1},h

from X

c−2

×S

to {0, 1},f

from X

×S

to Y, f

from X

c−1

×S

to Y ,and

from X

c−2

× S

to Y , such that (5.2) and (5.3) hold, where h

is deﬁned

by (5.4).

Proof.SinceM , i.e., SIM(M

,f), is a semi-input-memory ﬁnite automa-

ton and M

is strongly cyclic, M is strongly connected. Using Theorem 2.2.2,

M is a feedforward inverse with delay 2 if and only if M is invertible with

delay 2. From Theorem 5.4.1, M is a feedforward inverse with delay 2 if and

only if one of the conditions (a), (b) and (c) holds. 

We discuss brieﬂy h

and h

in (5.2). Suppose that (5.2) holds for any

−1

, ..., x

−c

in X and any s

in S

.Thenwehave

−2

,...,x

−c

)=h

−2

,...,x

−c

)

∨ (h

(0,x

−2

,...,x

−c+1

,δ

)) ⊕ 1)

∨ (h

(1,x

−2

,...,x

−c+1

,δ

)) ⊕ 1),

−3

,...,x

−c

)=h

−3

,...,x

−c

)

&(h

−3

,...,x

−c

, 0,δ

−1

)) ⊕ 1)

&(h

−3

,...,x

−c

, 1,δ

−1

)) ⊕ 1),

where ∨ stands for the logical-or operation, that is, 1 ∨ 1=1∨ 0=0∨ 1=

1, 0 ∨ 0 = 0. Conversely, given arbitrarily single-valued mappings h



from

c−1

× S

to {0, 1} and h



from X

c−2

× S

to {0, 1}, deﬁne

−2

,...,x

−c

)=h



−2

,...,x

−c

)

∨ (h



(0,x

−2

,...,x

−c+1

,δ

)) ⊕ 1)

∨ (h



(1,x

−2

,...,x

−c+1

,δ

)) ⊕ 1),

−3

,...,x

−c

)=h



−3

,...,x

−c

) (5.5)

&(h

−3

,...,x

−c

, 0,δ

−1

)) ⊕ 1)

&(h

−3

,...,x

−c

, 1,δ

−1

)) ⊕ 1).

It is easy to see that h

and h

satisfy (5.2). We conclude that h

and h

satisfy (5.2) if and only if h

and h

can be deﬁned by (5.5).

Historical Notes 175

Historical Notes

The structure of feedforward inverse ﬁnite automata is ﬁrst studied in [100]

for delay 0 and for delay 1 in binary case. References [4, 5, 146] present a

characterization for feedforward inverse ﬁnite automata with delay 1 of which

sizes of the input and output alphabets are the same, and [129] introduces

another characterization of them by means of mutual invertibility. Reference

[153] gives the ﬁrst characterization for binary feedforward inverse ﬁnite au-

tomata with delay 2, and [130] gives another characterization of them by

means of mutual invertibility. Reference [141] deals with the structure of bi-

nary feedforward inverse ﬁnite automata with delay 3. Sections 5.1 and 5.2

are based on [100]. Section 5.3 is based on [129]. And Sect. 5.4 is based on

[130].

6. Some Topics on Structure Problem

Renji Tao

Institute of Software, Chinese Academy of Sciences

Beijing 100080, China trj@ios.ac.cn

Summary.

This chapter investigates the following problem: given an invertible

(respectively inverse, weakly invertible, weak inverse, and feedforward in-

vertible) ﬁnite automaton, characterize the structure of the set of all its in-

verses (respectively original inverses, weak inverses, original weak inverses

and weak inverses with bounded error propagation).

To characterize the set of all inverses (or weak inverses, or weak inverses

with bounded error propagation) of a given ﬁnite automaton, the measures

are, loosely speaking, ﬁrst taking one member in the set and making a

partial ﬁnite automaton by restricting its inputs, then constructing the

set from this partial ﬁnite automaton. As an auxiliary tool, partial ﬁnite

automata and partial semi-input-memory ﬁnite automata are deﬁned.

To characterize the set of all original inverses (or original weak inverses)

of a given ﬁnite automaton, we use the state tree method and results in

Sect. 1.6 of Chap. 1.

Key words: inverses, weak inverses, original inverses, original weak in-

verses, bounded error propagation

This chapter investigates the following problem: given an invertible (respec-

tively inverse, weakly invertible, weak inverse, feedforward invertible) ﬁnite

automaton, characterize the structure of the set of all its inverses (respec-

tively original inverses, weak inverses, original weak inverses, weak inverses

with bounded error propagation).

To characterize the set of all inverses (or weak inverses, or weak inverses

with bounded error propagation) of a given ﬁnite automaton, the measures

are, loosely speaking, ﬁrst taking one member in the set and making a partial

ﬁnite automaton by restricting its inputs, then constructing the set from this

partial ﬁnite automaton. As an auxiliary tool, partial ﬁnite automata and

partial semi-input-memory ﬁnite automata are deﬁned.

178 6. Some Topics on Structure Problem

To characterize the set of all original inverses (or original weak inverses) of

a given ﬁnite automaton, we use the state tree method and results in Sect. 1.6

of Chap. 1.

6.1 Some Variants of Finite Automata

6.1.1 Partial Finite Automata

A partial ﬁnite automaton is a quintuple X, Y, S,δ, λ,whereX, Y and S are

nonempty ﬁnite sets, δ is a single-valued mapping from a subset of S × X to

S,andλ is a single-valued mapping from a subset of S ×X to Y . X, Y and S

are called the input alphabet,theoutput alphabet and the state alphabet of the

partial ﬁnite automaton, respectively; and δ and λ are called the next state

function and the output function of the partial ﬁnite automaton, respectively.

A partial ﬁnite automaton may naturally be expanded to a ﬁnite automa-

ton. Taken a special symbol, say

, to stand for the “undeﬁned symbol”, which

is not in S or Y . Denote the domain of δ by Δ and the domain of λ by Λ.

Let

δ(s, x)=

, if (s, x) ∈ (S × X) \ Δ or s = ,

λ(s, x)=

, if (s, x) ∈ (S × X) \ Λ or s = .

X, Y ∪{

},S ∪{},δ,λ is a ﬁnite automaton, and is called the trivial ex-

pansion of M .

By expanding domains of δ and λ of the trivial expansion of the partial

ﬁnite automaton M, the domain of δ of M may be expanded to (S∪{

})×X

∗

;

the domain of λ of M may be expanded to (S ∪{

}) × (X

∗

∪ X

Let s ∈ S and α ∈ X

∗

.If|α| > 0 yields δ(s, α

) ∈ S,whereα

is the preﬁx

of α of length |α|−1, we say that α is applicable to s. Clearly, if |α|  1, then

α is applicable to s.

Let α = a

...a

and β = b

...b

,wherea

,...,a

∈ Y ∪{}.If

for any i,1 i  r, a

= and b

= implies a

= b

,wesaythatα and

β are compatible, denoted by α ≈ β. If for any i,1 i  r, b

= implies

= b

,wesaythatα is stronger than β, denoted by β ≺ α. Notice that

the relation ≈ over words is reﬂexive and symmetric and the relation ≺ over

words is reﬂexive and transitive. It is easy to see that α ≺ β and β ≺ α if

and only if α = β.

Let M = X, Y, S, δ, λ be a partial ﬁnite automaton. For any states s

and s

of M, if for any α in X

∗

,thatα is applicable to s

and s

implies

that λ

,α) ≈ λ

,α), we say that s

and s

are compatible, denoted by

≈ s

. Notice that the relation ≈ over states is reﬂexive and symmetric. It

6.1 Some Variants of Finite Automata 179

is easy to see that for any s

, s

in S and any α in X

∗

,ifs

≈ s

and δ(s

,α)

is deﬁned, i =1, 2, then δ(s

,α) ≈ δ(s

,α). For any nonempty subset T of S,

if any two states in T are compatible, T is called a compatible set of M.IfT

is a compatible set of M and for any T



, T ⊂ T



⊆ S, T



is not a compatible

set of M, T is called a maximum compatible set of M.

Let C

, ..., C

be k compatible sets of M .If∪

i=1

= S, and for any i,

1  i  k,andanyx in X, there exists j,1 j  k, such that δ(C

,x), i.e.,

{δ(s, x) | s ∈ C

,δ(s, x) is deﬁned}, is a subset of C

, the sequence C

, ...,

is called a closed compatible family of M. Notice that C

and C

may be

thesameset,i = h.

Let C

, ..., C

be a closed compatible family of M = X, Y, S, δ,λ.Let



= X, Y



= Y , S



= {c

,...,c



,x)=



, if δ(C

,x) = ∅,

undeﬁned, if δ(C

,x)=∅,



,x)=



λ(s, x), if ∃s

∈ C

& λ(s

,x) is deﬁned),

undeﬁned, otherwise,

i =1,...,k, x∈ X,

where j is an arbitrary integer satisfying δ(C

,x) ⊆ C

,ands is an arbitrary

state in C

such that λ(s, x) is deﬁned. Since C

is compatible, the value

of λ



,x) is independent of the selection of s.LetM



= X



,δ



,λ



.

Then M



is a partial ﬁnite automaton. We use M(C

,...,C

)todenotethe

set of all such M



Let M

= X

,δ

,λ

, i =1, 2 be two partial ﬁnite automata with

= X

.Lets

be in S

, i =1, 2. If for any α in X

∗

,thatα is applicable to

implies that α is applicable to s

and λ

,α) ≺ λ

,α), we say that

is stronger than s

, denoted by s

≺ s

. If for any s

in S

, there exists s

in S

such that s

≺ s

,wesaythatM

is stronger than M

, denoted by M

≺ M

. If for any α in X

∗

, α is applicable to s

if and only if α is applicable

to s

,andλ

,α)=λ

,α) whenever α is applicable to s

, s

and s

are

said to be equivalent, denoted by s

∼ s

. If for any s

in S

, there exists s

in S

such that s

∼ s

, and for any s

in S

, there exists s

in S

such that

∼ s

, M

and M

are said to be equivalent, denoted by M

∼ M

Similar to the case of ﬁnite automata, for any s

in S

,anys

in S

,and

any α in X

∗

,ifδ

,α), i =1, 2 are deﬁned and s

∼ s

,thenδ

,α) ∼

,α). And for any s

in S

,anys

in S

,andanyα in X

∗

,ifδ

,α),

i =1, 2 are deﬁned and s

≺ s

,thenδ

,α) ≺ δ

,α).

From the deﬁnition, it is easy to show that for any positive integer k,any

in S

and any s

in S

, a suﬃcient and necessary condition of s

∼ s

180 6. Some Topics on Structure Problem

the following: for any α ∈ X

∗

with |α|  k, α is applicable to s

if and only

if α is applicable to s

, λ

,α)=λ

,α) whenever α is applicable to s

and for any α ∈ X

∗

with |α| = k, δ

,α) is deﬁned if and only if δ

,α)

is deﬁned, and δ

,α) ∼ δ

,α) whenever δ

,α) is deﬁned.

Notice that both the relation ≺ over states and the relation ≺ over partial

ﬁnite automata are reﬂexive and transitive, and both the relation ∼ over

states and the relation ∼ over partial ﬁnite automata are reﬂexive, symmetric

and transitive. It is easy to see that s

∼ s

if and only if s

≺ s

and s

≺

We point out that in the case of ﬁnite automata, relations s

≺ s

, s

≈

and s

∼ s

are the same.

Let M

= X

,δ

,λ

, i =1, 2 be two partial ﬁnite automata with

= X

. Assume that for any i,1 i  2, any s

in S

and any x in X

,x) is deﬁned if and only if λ

,x) is deﬁned. Then for any s

in S

i =1, 2, s

∼ s

if and only if for any α in X

∗

, λ

,α) is deﬁned (i.e., each

letter in λ

,α) is deﬁned) if and only if λ

,α) is deﬁned, and λ

,α)=

,α) whenever they are deﬁned. In fact, s

∼ s

if and only if for any α in

∗

and any x in X

, αx is applicable to s

if and only if αx is applicable to s

and for any α in X

∗

and any x in X

, λ

,αx)=λ

,αx) whenever αx

is applicable to s

. From the assumption that λ

,α) is deﬁned if and only

if δ

,α) is deﬁned, αx is applicable to s

if and only if λ

,α) is deﬁned.

Thus the condition that for any α in X

∗

and any x in X

, αx is applicable

to s

if and only if αx is applicable to s

, is equivalent to the condition

that for any α in X

∗

, λ

,α) is deﬁned if and only if λ

,α) is deﬁned.

Similarly, the condition that for any α in X

∗

and any x in X

, λ

,αx)=

,αx) whenever αx is applicable to s

, is equivalent to the condition that

for any α in X

∗

and any x in X

, λ

,αx)=λ

,αx) whenever λ

,α)

is deﬁned. Therefore, s

∼ s

if and only if for any α ∈ X

∗

, λ

,α)is

deﬁned if and only if λ

,α) is deﬁned, and for any α ∈ X

∗

and x ∈ X

,αx)=λ

,αx) whenever λ

,α) is deﬁned. Thus s

∼ s

if and

only if for any α ∈ X

∗

, λ

,α) is deﬁned if and only if λ

,α) is deﬁned,

and for any α ∈ X

∗

and x ∈ X

, λ

,αx)=λ

,αx) whenever λ

,α)

and λ

,α) are deﬁned. We conclude that s

∼ s

if and only if for any α

in X

∗

, λ

,α) is deﬁned if and only if λ

,α) is deﬁned, and λ

,α)=

,α) whenever they are deﬁned.

Let M

= X

,δ

,λ

, i =1, 2 be two partial ﬁnite automata with

= X

. Assume that for any i,1 i  2, any s

in S

and any x in X

,x) is deﬁned if and only if λ

,x) is deﬁned. Then for any s

in S

i =1, 2, s

≺ s

if and only if for any α in X

∗

, λ

,α) is deﬁned and

,α)=λ

,α) whenever λ

,α) is deﬁned. In fact, s

≺ s

if and

only if for any α in X

∗

and any x in X

, αx is applicable to s

and λ

,αx)

6.1 Some Variants of Finite Automata 181

≺ λ

,αx) whenever αx is applicable to s

.Thuss

≺ s

ifandonlyiffor

any α in X

∗

and any x in X

, λ

,α) is deﬁned and λ

,αx) ≺ λ

,αx)

whenever λ

,α) is deﬁned. Therefore, s

≺ s

if and only if for any α in X

∗

and any x in X

, λ

,αx) is deﬁned and λ

,αx)=λ

,αx) whenever

,αx) is deﬁned. It follows that s

≺ s

if and only if for any α in X

∗

,α) is deﬁned and λ

,α)=λ

,α) whenever λ

,α) is deﬁned.

Let M

= X

,δ

,λ

, i =1, 2 be two partial ﬁnite automata with

= X

. Assume that for any i,1 i  2, any s

in S

and any x in X

,x) is deﬁned if and only if λ

,x) is deﬁned. It is easy to show that

for any positive integer k,anys

in S

and any s

in S

,asuﬃcientand

necessary condition of s

∼ s

is the following: for any α ∈ X

∗

with |α|  k,

,α) is deﬁned if and only if λ

,α) is deﬁned, λ

,α)=λ

,α)

whenever they are deﬁned, and δ

,α) ∼ δ

,α) whenever δ

,α)is

deﬁned and |α| = k.

Lemma 6.1.1. Let M

= X, Y

,δ

,λ

 be a partial ﬁnite automaton and

∈ S

, i =1, 2.

(a) For any s

∈ S

, i =1, 2,andanyα ∈ X

∗

,ifs

≺ s

and δ

,α)

is deﬁned, then δ

,α) is deﬁned and δ

,α) ≺ δ

,α).

(b) For any s

, s

∈ S

,andanys

∈ S

,ifs

≺ s

and s

≺ s

,then

≈ s

Proof. (a) Let β ∈ X

∗

be applicable to δ

,α). Then αβ is applicable

to s

.Froms

≺ s

, αβ is applicable to s

and λ

,αβ) ≺ λ

,αβ).

Take β

∈ X. Clearly, β

is applicable to δ

,α). Thus αβ

is applicable

to s

. It follows that δ

,α) is deﬁned. Since αβ is applicable to s

, β is

applicable to δ

,α). Since λ

,αβ) ≺ λ

,αβ), we have λ

(δ

,α),β)

≺ λ

(δ

,α),β). Therefore, δ

,α) ≺ δ

,α).

(b) Let α in X

∗

be applicable to s

and s

.Sinces

≺ s

and s

≺ s

, α

is applicable to s

and λ

,α) ≺ λ

,α), i =0, 1. It follows that λ

,α)

≈ λ

,α). Therefore, s

≈ s

. 

Lemma 6.1.2. Let M = X, Y, S, δ, λ be a partial ﬁnite automaton, and

, ..., C

a closed compatible family of M. For any M



= X, Y, {c

,...,c



,λ



 in M(C

,...,C

) and any s in C

, 1  i  k, we have s ≺ c

Proof. We prove by induction on the length of α that for any i,1 i  k,

any s in C

,andanyα in X

∗

,ifα is applicable to s,thenα is applicable

to c

and λ(s, α) ≺ λ



,α). Basis : |α|  1. Clearly, α is applicable to

s and c

. From the deﬁnition of λ



,itisevidentthatλ(s, α) ≺ λ



,α).

Thus s ≺ c

. Induction step : Suppose that for any α of length j( 1) the

proposition has been proven. To prove the case j +1, let s ∈ C

and α ∈

∗

with |α| = j + 1. Suppose that α is applicable to s.Letα = xα



,where

182 6. Some Topics on Structure Problem

x ∈ X.Then|α



| = j.Since|α



|  1, δ(s, x) is deﬁned. From the deﬁnition

of δ



, δ



,x) is deﬁned and δ(s, x) ∈ C

,wherec

= δ



,x). Since α is

applicable to s, α



is applicable to δ(s, x). From the induction hypothesis,



is applicable to δ



,x)andλ(δ(s, x),α



) ≺ λ



(δ



,x),α



). Since s ∈ C

we have λ(s, x) ≺ λ



,x). It follows that λ(s, α)=λ(s, x)λ(δ(s, x),α



) ≺



,x)λ



(δ



,x),α



)=λ



,α). 

Theorem 6.1.1. Let M be a partial ﬁnite automaton, and C

, ..., C

closed compatible family of M. For any M



in M(C

,...,C

), we have M ≺



Proof.LetM



= X, Y, {c

,...,c

},δ



,λ



.Since∪

i=1

is the state al-

phabet of M, for any state s of M, there exists i,1 i  k, such that s ∈

. From Lemma 6.1.2, we have s ≺ c

. Therefore, M ≺ M



. 

Let M

= X

,δ

,λ

, i =1, 2 be two partial ﬁnite automata. If

⊆ X

, Y

⊆ Y

, S

⊆ S

, and for any s in S

and any x in X

,thatδ

(s, x)

is deﬁned implies that δ

(s, x) is deﬁned and δ

(s, x)=δ

(s, x), and that

(s, x)isdeﬁnedimpliesthatλ

(s, x) is deﬁned and λ

(s, x)=λ

(s, x), M

is called a partial ﬁnite subautomaton of M

, denoted by M

 M

. For any

nonempty subset S



of S

and any nonempty subset X



of X

,ifδ



| there exist s

∈ S



and x ∈ X

such that s



= δ

,x) ∈ S

}⊆S



, S



is said to be closed with respect to X



in M

. Clearly, if S



is closed with

respect to X



in M

,thenX



, Y

, S



, δ



×X



, λ



×X



 is a partial ﬁnite

subautomaton of M

,whereδ



×X



and λ



×X



are restrictions of δ

and

on S



× X



, respectively.

Notice that the relation  on partial ﬁnite automata is reﬂexive and

transitive. It is easy to see that M

 M

implies M

≺ M

inthecaseof

= X

Let M

= X

,δ

,λ

, i =1, 2 be two partial ﬁnite automata. M

and M

are said to be isomorphic,ifX

= X

, Y

= Y

and there exists

a one-to-one mapping ϕ from S

onto S

such that for any s

in S

and

any x in X

, δ

,x) is deﬁned if and only if δ

(ϕ(s

),x) is deﬁned, and

ϕ(δ

,x)) = δ

(ϕ(s

),x) whenever they are deﬁned, and λ

,x)isdeﬁned

if and only if λ

(ϕ(s

),x) is deﬁned, and λ

,x)=λ

(ϕ(s

),x) whenever

they are deﬁned. ϕ is called an isomorphism from M

to M

Notice that the isomorphic relation on partial ﬁnite automata is reﬂexive,

symmetric and transitive. Clearly, if M

and M

are isomorphic, then M

∼

and M

≺ M

Theorem 6.1.2. Let M = X, Y, S, δ, λ and M



= X



,δ



,λ



 be

two partial ﬁnite automata. If M ≺ M



and Y = Y



, then there exist a

partial ﬁnite subautomaton M



of M



, a closed compatible family C

, ...,

6.1 Some Variants of Finite Automata 183

of M, and a partial ﬁnite automaton M



in M(C

,...,C

) such that M



and M



are isomorphic.

Proof. Suppose that M ≺ M



.ThenX = X



.LetS



= {s



| s



∈



, ∃s(s ∈ S & s ≺ s



)}. For any s



in S



,letψ(s



)={s | s ∈ S, s ≺ s



Clearly, ψ(s



) = ∅.FromM ≺ M



,wehave∪



∈S



ψ(s



)=S.From

Lemma 6.1.1 (b), for any s



in S



, ψ(s



) is a compatible set of M.Lets



∈ S



, x ∈ X,andδ(ψ(s



),x) = ∅.Lets be in ψ(s



), so that δ(s, x)is

deﬁned. Since s ≺ s



, from Lemma 6.1.1 (a), δ





,x) is deﬁned and δ(s, x)

≺ δ





,x). Thus δ(ψ(s



),x) ⊆ ψ(δ





,x)). Let states of S



be s



, ...,



,wherek = |S



|.LetC

= ψ(s



), i =1,...,k. We conclude that the

sequence C

, ..., C

is a closed compatible family of M.

We construct a partial ﬁnite automaton M



= X





,δ



,λ



 as

follows. For any s



in S



and any x in X, whenever δ(C

,x) = ∅,there

exists s in ψ(s



) such that δ(s, x) is deﬁned. In the preceding paragraph,

we have proven that for any s



∈ S



and any x ∈ X, δ(ψ(s



),x) = ∅

yields δ(ψ(s



),x) ⊆ ψ(δ





,x)). Thus δ(ψ(s



),x) ⊆ ψ(δ





,x)). Since

δ(ψ(s



),x)=δ(C

,x) = ∅, δ





,x) is deﬁned and in S



.Ifδ(C

,x) = ∅,

we deﬁne δ



,x)=δ





,x); otherwise, δ



,x) is undeﬁned. Whenever

there exists s in C

such that λ(s, x) is deﬁned, since x is applicable to s and

s ≺ s



,wehaveλ(s, x) ≺ λ





,x). It follows that λ





,x) is deﬁned and

λ(s, x)=λ





,x). If there exists s in C

such that λ(s, x) is deﬁned, we

deﬁne λ



,x)=λ





,x); otherwise, λ



,x) is undeﬁned. It is easy to

see that M



is a partial ﬁnite subautomaton of M



Take a partial ﬁnite automaton X, Y, S



,δ



,λ



 in M(C

,...,C

)asM



where S



= {c

,...,c



,x)=



, if δ(C

,x) = ∅,

undeﬁned, if δ(C

,x)=∅,



,x)=



λ(s, x), if ∃s

∈ C

& λ(s

,x) is deﬁned),

undeﬁned, otherwise,

i =1,...,k, x∈ X,

j is the integer satisfying δ





,x)=s



,ands is an arbitrary state in C

such that λ(s, x) is deﬁned. In the ﬁrst paragraph of the proof, we have proven

that for any s



∈ S



and any x ∈ X, δ(ψ(s



),x) = ∅ yields δ(ψ(s



),x) ⊆

ψ(δ





,x)). From δ





,x)=s



,wehaveδ(ψ(s



),x) ⊆ ψ(δ





,x)) =

ψ(s



), that is, δ(C

,x) ⊆ C

.ThusM



is in M(C

,...,C

) indeed.

We prove that M



and M



are isomorphic. Let ϕ(c

)=s



, i =1,...,k.

Clearly, ϕ is a one-to-one mapping from S



onto S



. From the constructions

of M



and M



,itiseasytoseethatδ



,x) is deﬁned if and only if