Tao R. Finite Automata and Application to Cryptography

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

184 6. Some Topics on Structure Problem



,x) is deﬁned, and that whenever they are deﬁned, δ



,x)=s



and only if δ



,x)=c

. Similarly, λ



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



,x)

is deﬁned, and whenever they are deﬁned, λ



,x)=λ



,x). Thus ϕ is an

isomorphism from M



to M



. We conclude that M



and M



are isomorphic.



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



= Y,X,S



,δ



,λ





a partial ﬁnite automaton. For any states s in S and s



in S



,if

(∀α)

(∃α

)

(X∪{ })

∗

[ λ



,λ(s, α)) = α

α & |α

| = τ ],



,s) is called a match pair with delay τ or say that s



τ-matches s. Clearly,

if s



τ-matches s and β = λ(s, α)forsomeα in X

∗

,thenδ



,β) τ-matches

δ(s, α). M



is called a weak inverse with delay τ of M, if for any s in S,there

exists s



in S



such that (s



,s)isamatchpairwithdelayτ .

Let M = X, Y, S, δ, λ be a partial ﬁnite automaton. The states of M

is said to be reachable from a state s (respectively from a subset I of S),

if for any state s



in S, there exists α in X

∗

such that s



= δ(s, α)holds

(respectively holds for some s in I).

6.1.2 Nondeterministic Finite Automata

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

Y and S are nonempty ﬁnite sets, δ is a single-valued mapping from S × X

to 2

\{∅},andλ is a single-valued mapping from S × X to 2

\{∅},where

stands for the power set of a set T ,thatis,2

= {T



| T



⊆ T }. X, Y and

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

the nondeterministic ﬁnite automaton, respectively; and δ and λ are called

the next state function and the output function of the nondeterministic ﬁnite

automaton, respectively.

The domain of δ may be expanded to S × X

∗

as follows.

δ(s, ε)={s},

δ(s, αx)=δ(δ(s, α),x), i.e., ∪



∈δ(s,α)

δ(s



,x),

s ∈ S, α ∈ X

∗

,x∈ X.

It is easy to see that for any s

∈ S and any x

,...,x

l−1

∈ X, s

∈

δ(s

...l

l−1

) if and only if there exist s

,...,s

l−1

∈ S such that s

i+1

∈

δ(s

), i =0, 1,...,l− 1.

The domain of λ may be expanded to S × (X

∗

∪ X

) as follows. For any

state s

∈ S and any l input letters x

,...,x

l−1

∈ X, λ(s

...x

l−1

)

is a subset of the set of all the sequences of length l over Y satisfying the

6.2 Inverses of a Finite Automaton 185

condition: for any y

, y

, ..., y

l−1

in Y , y

...y

l−1

is in λ(s

...x

l−1

)

if and only if there exist s

, i =1, 2,...,l− 1inS such that

i+1

∈ δ(s

),i=0, 1,...,l− 2

and

∈ λ(s

),i=0, 1,...,l− 1.

Inthecaseofl =0,x

...x

l−1

and y

...y

l−1

mean the empty word

ε. For any state s

∈ S and any inﬁnite input letters x

,... ∈ X,

λ(s

...) is a subset of Y

satisfying the condition: for any y

, y

, ...

in Y , y

... is in λ(s

...) if and only if for any l  0, y

...y

l−1

in λ(s

...x

l−1

Let M = X, Y, S, δ, λ be a nondeterministic ﬁnite automaton, and M



Y , X, S



, δ



, λ



 a ﬁnite automaton. For any states s in S and s



in S



,s)iscalledamatch pair with delay τ or say that s



τ-matches s,if

for any l  τ,anyx

,...,x

,...,z

in X and any y

,...,y

in Y , y

...y

∈ λ(s, x

...x

)andz

...z

= λ



...y

) yield

τ+1

...z

= x

...x

l−τ

. M



is called an inverse with delay τ of M,iffor

any s in S and any s



in S



,(s



,s)isamatchpairwithdelayτ. M



is called

a weak inverse with delay τ of M, if for any s in S, there exists s



in S



such

that (s



,s)isamatchpairwithdelayτ .

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



= Y,X,S



,δ



,λ





a nondeterministic ﬁnite automaton. For any states s in S and s



in S



,s)iscalledamatch pair with delay τ or say that s



τ-matches s,if

for any l  τ,anyx

,...,x

,...,z

in X and any y

,...,y

in Y , y

...y

= λ(s, x

...x

)andz

...z

∈ λ



...y

) yield

τ+1

...z

= x

...x

l−τ

. M



is called an inverse with delay τ of M,iffor

any s in S and any s



in S



,(s



,s)isamatchpairwithdelayτ.

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



= X, Y



,δ



,λ





a nondeterministic ﬁnite automaton. For any states s in S and s



in S



,iffor

any α ∈ X

∗

, λ(s, α)isinλ



,α), s



is said to be 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



. It is easy to verify that whenever



is a ﬁnite automaton also, s ≺ s



if and only if s ∼ s



, and the deﬁnition

of M ≺ M



here coincides with the deﬁnition in Sect. 1.2 of Chap. 1.

6.2 Inverses of a Finite Automaton

For any ﬁnite automaton M = X, Y, S, δ, λ,letδ

be a single-valued map-

ping from 2

× Y to 2

, deﬁned by

186 6. Some Topics on Structure Problem

(T,y)={δ(s, x) | s ∈ T,x ∈ X, y = λ(s, x)},

T ⊆ S, y ∈ Y.

Notice that δ

(T,y)=∅ holds if y = λ(s, x) holds for any s ∈ T and any

x ∈ X. Expand the domain of δ

to 2

× Y

∗

as follows:

(T,ε)=T,

(T,βy)=δ

(δ

(T,β),y),

T ⊆ S, β ∈ Y

∗

,y∈ Y.

It is easy to prove by induction on l that for any T

⊆ S,andanyy

,...,

l−1

∈ Y , δ

...y

l−1

)=T

if and only if there exist subsets T

, ...,

l−1

of S such that T

i+1

= δ

), i =0, 1,...,l − 1. It immediately

follows that δ

(T,αβ)=δ

(δ

(T,α),β) holds for any T ⊆ S and any α,

β ∈ Y

∗

. Moreover, we can prove by induction on l the following assertion:

for any T

⊆ S and any y

, ..., y

l−1

∈ Y ,ifδ

...y

l−1

) = ∅,thenfor

any s

in δ

...y

l−1

) there exist s

in T

and α in X

∗

of length l such

that s

= δ(s

,α)andy

...y

l−1

= λ(s

,α). Conversely, it is evident that for

any T

⊆ S and any y

, ..., y

l−1

∈ Y , if there exist s

in T

and α in X

∗

of length l such that y

...y

l−1

= λ(s

,α), then δ

...y

l−1

) = ∅ and

δ(s

,α) ∈ δ

...y

l−1

Given an invertible ﬁnite automaton M = X, Y, S, δ,λ with delay τ ,

without loss of generality, we assume λ(S, X)=Y .

Let R

= {λ(s, α) | s ∈ S, α ∈ X

∗

}.LetM

out

= Y, 2

,δ

,S,S

{∅} be a ﬁnite automaton recognizer, where S

= {δ

(S, β) | β ∈ Y

∗

We prove that M

out

recognizes R

. Suppose y

...y

l−1

∈ R

. Then there

exist s

∈ S and α ∈ X

∗

such that y

...y

l−1

= λ(s

,α). It follows that

(S, y

...y

l−1

) = ∅.Thusδ

(S, y

...y

l−1

) ∈ S

. Conversely, suppose

(S, y

...y

l−1

) ∈ S

.Thenδ

(S, y

...y

l−1

) = ∅. Take arbitrarily a state

in δ

(S, y

...y

l−1

). Then there exist s

in S and α in X

∗

of length l such

that s

= δ(s

,α)andy

...y

l−1

= λ(s

,α). It follows that y

...y

l−1

∈ R

We conclude that M

out

recognizes R

. Point out that if β ∈ R

, then there

exists y ∈ Y such that βy ∈ R

Let M



= Y,X,S



,δ



,λ



 be an inverse ﬁnite automaton with delay τ of

M. We construct a partial ﬁnite automaton



= Y,X,



 from M



and M,where



= {δ

(S, β),δ



,β)|s



∈ S



,β ∈ Y

∗

,δ

(S, β) = ∅},



(t, s



,y)=



δ

(t, y),δ



,y), if δ

(t, y) = ∅,

undeﬁned, otherwise,

6.2 Inverses of a Finite Automaton 187



(t, s



,y)=





,y), if δ

(t, y) = ∅,

undeﬁned, otherwise,

t, s



∈



,y∈ Y.



is referred to as the input restriction of M



by M .

Clearly, for any state t, s



 of



and any β ∈ Y

∗



(t, s



,β)=

δ

(t, β), δ



,β) and



(t, s



,β)=λ



,β) whenever δ

(t, β) = ∅;



(t, s



,β)and



(t, s



,β) are undeﬁned whenever δ

(t, β)=∅,where



(t, s



,β) is deﬁned if and only if each letter of



(t, s



,β) is deﬁned.

Thus we have t, s



≺s



It is easy to show that S

⊆ S

yields S



≺S



, s



∈ S



, S

∈

\{∅}.

States of



are reachable from {S, s



,s



∈ S



}. In fact, from the de-

ﬁnition of



, for any state ¯s



, there exist s



∈ S



and β ∈ Y

∗

such

that ¯s



= δ

(S, β),δ



,β) and δ

(S, β) = ∅.Fromδ

(S, β),δ



,β) =



(S, s



,β), for any state ¯s



, there exist a state S, s



 of



and

β ∈ Y

∗

such that ¯s



(S, s



,β).

Let



= {



(¯s



,β) | ¯s



∈



,β ∈ Y

∗

, |β| = τ}. Clearly,



is closed with

respect to Y in



.Weuse



to denote the partial ﬁnite subautomaton

Y , X,



×Y



×Y

 of



is referred to as the τ-successor of



Let M



= Y,X,S



,δ



,λ



 be an inverse ﬁnite automaton with delay τ .

Similarly, from M



and M we can construct



, the input restriction of M



by M ,and



,theτ -successor of



Lemma 6.2.1. If M



and M



are inverse ﬁnite automata with delay τ of

M,then



and



are equivalent.

Proof.Let¯s



be a state of



. Then there exist ¯s



and β

of length

τ in Y

∗

such that ¯s



(¯s



,β

). From the construction of



, there exist



in S



and β of length  τ in R

such that ¯s



(S, s



,β). Let ¯s



(S, s



,β), where s



is an arbitrarily ﬁxed state in S



.Weprove¯s



∼ ¯s



For any β

in Y

∗

,wehave



(S, s



,ββ





,β)λ



(δ



,β),β

), if δ

(S, ββ

) = ∅,

undeﬁned, otherwise,



(S, s



,ββ





,β)λ



(δ



,β),β

), if δ

(S, ββ

) = ∅,

undeﬁned, otherwise,

where “undeﬁned” means that some letter is undeﬁned. Noticing that M

out

recognizes R

,whenδ

(S, ββ

) = ∅, there exist s in S and α in X

∗

such

188 6. Some Topics on Structure Problem

that λ(s, α)=ββ

.SinceM



and M



are inverse ﬁnite automata with delay

τ of M ,wehave



,β)λ



(δ



,β),β

)=λ



,ββ

)

= λ



,λ(s, α)) = x



−τ

...x



−1

...x

r−τ

and



,β)λ



(δ



,β),β

)=λ



,ββ

)

= λ



,λ(s, α)) = x



−τ

...x



−1

...x

r−τ

for some x



−τ

, ..., x



−1

, x



−τ

, ..., x



−1

in X,wherer = |α|−1, x

, x

, ...,

r−τ

∈ X,andx

...x

r−τ

is a preﬁx of α.From|β|  τ, it follows that



(δ



,β),β

)=λ



(δ



,β),β

). Since



(¯s



, β

)=λ



(δ



, β), β

)and



(¯s



, β

)=λ



(δ



, β), β

), we obtain



(¯s



,β



(¯s



,β

). When

(S, ββ

)=∅,



(S, s



,ββ

)and



(S, s



,ββ

) are undeﬁned. Since



(S, s



,β)=¯s



and



(S, s



,β)=¯s





(S, s



,β)and



(S, s



, β)are

deﬁned. Therefore,



(¯s



,β

)and



(¯s



,β

) are undeﬁned. We conclude that

¯s



and ¯s



are equivalent.

From symmetry, for any ¯s



there exists ¯s



such that ¯s



and ¯s



are equivalent. Thus



and



are equivalent. 

Since M is invertible with delay τ, there exists a τ -order input-memory

ﬁnite automaton which is an inverse with delay τ of M.Givenaτ-order

input-memory ﬁnite automaton, say M



, assume that M



is an inverse with

delay τ of M.Let



be the input restriction of M



by M,and



the

τ-successor of



We use T



(Y,τ − 1) to denote a labelled tree with level τ − 1inwhich

any vertex with level <τ emits |Y | arcs labelled by diﬀerent letters in Y ,

respectively. Such labels are called input labels of arcs. For each vertex v of



(Y,τ − 1), the sequence of labels of arcs in the unique path from the root of



(Y,τ − 1) to the vertex v is called the input label sequence of the vertex v.

Let T (Y,τ−1)bethesubtreeofT



(Y,τ−1) satisfying the following condition:

avertexofT



(Y,τ − 1) is a vertex of T (Y, τ − 1) if and only if its input label

sequence is in R

. From the deﬁnition of R

, βy ∈ R

yields β ∈ R

for

any β ∈ Y

∗

and any y ∈ Y . Therefore, T (Y,τ − 1) is a tree indeed and the

root of T(Y, τ − 1) is the root of T



(Y,τ − 1). Since for any β ∈ Y

∗

, β ∈ R

yields βy ∈ R

for some y ∈ Y , any vertex with level <τ of T (Y,τ − 1)

emits at least one arc. It is easy to see that in the case of λ(S, X)=Y ,the

root of T (Y,τ − 1) emits |Y | arcs of which input labels consist of diﬀerent

letters in Y . For each arc of T (Y,τ − 1), we assign a letter in X to it as its

output label. Diﬀerent assignments of the output labels give diﬀerent trees;

the set of all such trees is denoted by T



(Y,X,τ − 1). Let T



(Y,X,τ − 1) be

6.2 Inverses of a Finite Automaton 189

a non-empty subset of T



(Y,X,τ − 1). We “join” trees in T



(Y,X,τ − 1) to

the partial ﬁnite automaton



to get a partial ﬁnite automaton, say M



Y,X,S



,δ



,λ



, as follows. The state alphabet S



of M



is the union set



and all vertices with level <τ of all trees in T



(Y,X,τ − 1); we assume

that states in



and such vertices are diﬀerent from each other. For any state

t in S



and any y in Y , we deﬁne δ



(t, y)andλ



(t, y)asfollows.Inthecase

of t ∈



, deﬁne δ



(t, y)=



(t, y)andλ



(t, y)=



(t, y). In the case where t

is a vertex with level <τ−1ofsometreeinT



(Y,X,τ − 1), if there is an arc

with input label y emitted from t, then deﬁne δ



(t, y)=t



and λ



(t, y)=x,

where t



is the terminal vertex of the arc and x is the output label of the arc;

if there is no arc with input label y emitted from t,thenδ



(t, y)andλ



(t, y)

are undeﬁned. In the case where t is a vertex with level τ − 1 of some tree in



(Y,X,τ − 1), let y

, y

, ..., y

τ−2

be the input label sequence of arcs in the

path from the root to t. If there is an arc with input label y emitted from t,

then deﬁne δ



(t, y)=δ

(S, y

...y

τ−2

y), y, y

τ−2

,...,y

,astateof



and λ



(t, y)=x,wherex is the output label of the arc; if there is no arc

with input label y emitted from t,thenδ



(t, y)andλ



(t, y) are undeﬁned.

The states corresponding to roots of trees in T



(Y,X,τ − 1) are called root

states of M



.WeuseJ



(M,M



) to denote the set of all such M



For any M



in J



(M,M



), states of M



are reachable from root states

of M



. In fact, for any state t of M



, in the case where t is a vertex of

some tree with root t

,itisevidentthatthereexistsβ ∈ Y

∗

such that



,β)=t. Suppose that t ∈



. From the deﬁnition of



,thereex-

ist a state ¯s



and β

in Y

∗

such that |β

| = τ and



(¯s



,β

)=t.

From the deﬁnition of



, there exist a state S, s



 of



and β

in Y

∗

such that ¯s



= δ

(S, β

),δ



,β

).Thus¯s



(S, s



,β

). It follows that



(S, s



,β

)=t.Letβ

= β

with |β

| = τ ,and



(S, s



,β

)=¯s



Then ¯s



is a state of



,¯s



= δ

(S, β

), y

τ−1

,...,y

,and



(¯s



,β

)=t,

where β

= y

...y

τ−1

.Lett

be any root state of M



. From the construc-

tion of M



, noticing that β

∈ R

and β

is an input label sequence of trees

in T



(Y,X,τ − 1), we have δ



,β

)=¯s



. This yields that δ



,β



(δ



,β

),β

)=δ



(¯s



,β



(¯s



,β

)=t. We conclude that for any

state t of M



there exist a root state t

and β in Y

∗

such that δ



,β)=t.

Let

M = Y,X,

δ,

λ be a partial ﬁnite automaton such that

λ(s, y)

is deﬁned if and only if

δ(s, y) is deﬁned. Each state s

M determines a

labelled tree with level τ − 1, denoted by T

τ−1

), which can be recurrently

constructed from

M and s

as follows. We assign s

to the root of T

τ−1

)

temporarily. For any vertex with level <τ of T

τ−1

)andanyy in Y ,lets

be the label of the vertex. If

δ(s, y)isdeﬁned,thenanarcisemittedfromthe

vertex and y, called the input label, and

λ(s, y), called the output label, are

190 6. Some Topics on Structure Problem

assigned to the arc, and

δ(s, y) is temporarily assigned to the terminal vertex

of the arc. Finally, deleting all labels of vertices results the tree T

τ−1

We use J (M, M



) to denote the set of

M in J



(M,M



) satisfying the

following condition: for any states s

and s

M,ifs

is a root state and

is a successor state of s

, then there exists a root state s

M such that

τ−1

)isasubtreeofT

τ−1

Lemma 6.2.2. For any partial ﬁnite automaton

M = Y, X,

δ,

λ in

J (M,M



) and any state ˜s of

M, there exists a root state

t of

M such that

˜s ≺

Proof. Since states of

M are reachable from root states of

M, for any state

˜s of

M, there exist a root state

M and β ∈ Y

∗

such that

δ(

,β)=˜s.

It is suﬃcient to prove the following proposition: for any state ˜s of

M,any

root state

M and any β ∈ Y

∗

,if

δ(

,β)=˜s, then there exists a root

state

t of

M such that ˜s ≺

t. We prove the proposition by induction on the

length of β. Basis : |β| =0.˜s is a root state of

M. Take

t =˜s.Then˜s ≺

Induction step : Suppose that for any state ˜s of

M, any root state

and any β of length l in Y

∗

,if

δ(

,β)=˜s, then there exists a root state

t of

M such that ˜s ≺

t.Toprovethecaseof|β| = l + 1, suppose that

δ(

,β)=˜s,

|β| = l +1 and

is a root state of

M.Letβ = yβ

, y ∈ Y ,and

δ(

,y)=˜s

Since

M ∈J(M, M



), there exists a root state

M such that T

τ−1

(˜s

)isa

subtree of T

τ−1

(

). We prove ˜s

≺

.Letβ

be in Y

∗

. Suppose that

λ(˜s

,β

)

is deﬁned. In the case of |β

|  τ,sinceT

τ−1

(˜s

)isasubtreeofT

τ−1

(

λ(

,β

) is deﬁned and

λ(˜s

,β

λ(

,β

). In the case of |β

| >τ,let

= β

with |β

| = τ.Then

λ(˜s

,β

) is deﬁned. Since T

τ−1

(˜s

)isasubtree

of T

τ−1

(

λ(

,β

) is deﬁned and

λ(˜s

,β

λ(

,β

). Let

δ(˜s

,β

)=˜s

and

δ(

,β

)=˜s

.Then

δ(

,yβ

)=˜s

. From the construction of

M,we

have ˜s

= δ

(S, β

), y

τ−1

,...,y

 and ˜s

= δ

(S, yβ

), y

τ−1

,...,y

 =

δ

,β

), y

τ−1

,...,y

,whereS

= δ

(S, y), and β

= y

...y

τ−1

.From

⊆ S,wehaveδ

,β

) ⊆ δ

(S, β

). Notice that for any states S





and S



 of

M,ifS

⊆ S

,thenS



≺S



.Thus˜s

≺ ˜s

.Since

λ(˜s

,β

) is deﬁned and ˜s

δ(˜s

,β

λ(˜s

,β

) is deﬁned. From ˜s

≺ ˜s

λ(˜s

,β

) is deﬁned and

λ(˜s

,β

λ(˜s

,β

). Therefore,

λ(˜s

,β

λ(˜s

,β

)

λ(˜s

,β

λ(

,β

)

λ(˜s

,β

λ(

,β

). We conclude that ˜s

≺

.Since˜s

≺

and ˜s =

δ(˜s

,β

δ(

,β

) is deﬁned. Denoting ˜s

δ(

,β

), then ˜s ≺

˜s

.Since|β

| = l, from the induction hypothesis, there exists a root state

M such that ˜s

≺

.Using˜s ≺ ˜s

,wehave˜s ≺

. 

Lemma 6.2.3. For any ﬁnite automaton M



= Y,X,S



,δ



,λ



, M



an inverse with delay τ of M if and only if there exists

M in J (M, M



) such

that



and

M are equivalent, where



is the input restriction of M



6.2 Inverses of a Finite Automaton 191

Proof. only if : Suppose that M



is an inverse with delay τ of M.Let



= {T



τ−1

(S, s



) | s



∈ S



}. Clearly, T



⊆T



(Y,X,τ − 1). Joining

trees in T





results a partial ﬁnite automaton, say

M = Y,X,

δ,

λ,

where



is the τ-successor of



,and



is the input restriction of M



M. Clearly,

M is in J



(M,M



Below, the root state of

M corresponding to the root of T



τ−1

(S, s



)

is called the root state of

M corresponding to s



. (Root states of

corresponding to s



and s



may be the same for diﬀerent s



and s



For any s



in S



,if˜s is the root state of

M corresponding to s



,then

the state ˜s of

M and the state S, s



 of



are equivalent. To prove

this assertion, notice that the following fact is evident: for any β in Y

∗

with |β|  τ ,



(S, s



,β) is deﬁned if and only if

λ(˜s, β) is deﬁned,

and



(S, s



,β)=

λ(˜s, β) whenever they are deﬁned. We prove the fact

that



(S, s



,β) ∼

δ(˜s, β) holds for any β of length τ in R

.Let-

ting β ∈ R

and |β| = τ, from the proof of Lemma 6.2.1, we have



(S, s



,β) ∼



(S, s



,β) for any state s



of M



. From the construction of

M,wehave

δ(˜s, β)=δ

(S, β), y

τ−1

,...,y

,whereβ = y

...y

τ−1

.Since



(S, s



,β)=δ

(S, β), y

τ−1

,...,y

, from the construction of

M,itfol-

lows that



(S, s



,β) ∼

δ(˜s, β). Therefore,



(S, s



,β) ∼

δ(˜s, β). Using the

two facts mentioned above, since



(S, s



,β)and

δ(˜s, β) are undeﬁned for

β ∈ R

,thestate˜s of

M and the state S, s



 of



are equivalent.

Using the above assertion, for any state S, s



 of



, there exists a

state ˜s of

M such that ˜s ∼S, s



. Since states of



are reachable from

{S, s



,s



∈ S



}, for any state of



, there exists a state of

M such that

they are equivalent. Conversely, for any root state ˜s of

M, there exists a state

S, s



 of



such that ˜s ∼S, s



. Since states of



are reachable from

{S, s



,s



∈ S



}, states of



are reachable from

{



(S, s



,β),s



∈ S



,β ∈ R

, |β| = τ }

= {δ

(S, y

...y

τ−1

), y

τ−1

,...,y

,y

...y

τ−1

∈ R

From the construction of

M, states in {δ

(S, y

...y

τ−1

), y

τ−1

,...,y

,

... y

τ−1

∈ R

} are reachable from root states of

M. It follows that states

M are reachable from its root states. Thus for any state of

M, there exists

a state of



such that they are equivalent. We conclude



∼

We prove

M ∈J(M, M



). Suppose that ˜s is a root state of

M.From

the assertion shown previously, there exists s



in S



such that ˜s ∼S, s



.

For any y in Y ,if

δ(˜s, y) is deﬁned, then

δ(˜s, y) ∼



(S, s



,y). Clearly,



(S, s



,y)=δ

(S, y),δ



,y)≺S, δ



,y).Let

t be the root state

M corresponding to δ



,y). Then we have

t ∼S, δ



,y).Thus

δ(˜s, y) ≺

t. It follows that T

τ−1

(

δ(˜s, y)) is a subtree of T

τ−1

(

t). Therefore,

M ∈J(M, M



192 6. Some Topics on Structure Problem

if : Suppose that

M = Y,X,

δ,

λ∈J(M,M



)and



∼

M. For any s

in S,anys



in S



and any α = x

...x

,lety

...y

= λ(s, α)andz

...z



...y

), where x

, ..., x

∈ X, y

, ..., y

∈ Y ,andz

, ..., z

∈ X.We

prove z

...z

= x

...x

l−τ

if l  τ. Suppose that l  τ .Letβ

= y

...y

τ−1

= y

...y

,and¯s



= S, s



.Since



and

M are equivalent, there exists

˜s in

S such that ˜s ∼ ¯s



. Noticing that domains of



and



are the same and

that domains of

δ and

λ are the same, for any β in Y

∗



(¯s



,β) is deﬁned if

and only if

λ(˜s, β) is deﬁned, and



(¯s



,β)=

λ(˜s, β) holds whenever they are

deﬁned. Since β

, i.e., λ(s, α), is in R



(¯s



,β

) is deﬁned. It follows

that



(¯s



,β

λ(˜s, β

). From λ



,β



(¯s



,β

), it follows

that

λ(˜s, β

)

λ(

δ(˜s, β

),β

)=λ



,β

)=z

...z

. Therefore, we have

λ(

δ(˜s, β

),β

)=z

...z

. On the other hand, from the construction of

δ(˜s, β

)=¯s, y

τ−1

,...,y

 for some state ¯s, y

τ−1

,...,y

 in



.Thus

we have

λ(

δ(˜s, β

),β



(¯s, y

τ−1

,...,y

,β

)=λ



(y

τ−1

,...,y

,β

Since M



is an inverse with delay τ of M, for any state s



of M



,wehave



,β

)=x

−τ

...x

−1

...x

l−τ

for some x

−τ

,...,x

−1

in X.SinceM



is a

τ-order input-memory ﬁnite automaton, it follows that λ



(y

τ−1

,...,y

,β

...x

l−τ

.Thusz

...z

λ(

δ(˜s, β

),β

)=λ



(y

τ−1

,...,y

,β

)=x

...

l−τ

. Therefore, M



is an inverse with delay τ of M. 

For any partial ﬁnite automaton

M = Y, X,

δ,

λ in J (M, M



), each

root state

t determines a compatible set C(

t)={˜s | ˜s ∈

S, ˜s ≺

t}.For

any two diﬀerent root states

t and



M,if

t ≺



, then trees with

roots

t and



are the same. Thus each C(

t) only contains one root state.

From Lemma 6.1.1 (b), C(

t) is compatible. We use C(

M) to denote the set

{C(

t) |

t is a root state of

M}. For any C(

t)inC(

M)andanyy in Y ,us-

ing Lemma 6.1.1 (a), if

δ(C(

t),y) = ∅,then˜s ≺

δ(

t, y) holds for any ˜s in

δ(C(

t),y). Since

M is in J (M,M



), from Lemma 6.2.2, there exists a root

state

M such that

δ(

t, y) ≺

. It follows that ˜s ≺

holds for any ˜s

δ(C(

t),y). Thus

δ(C(

t),y) ⊆ C(

). Moreover, from Lemma 6.2.2, for any

state ˜s of

M, there exists a root state

t of

M such that ˜s ∈ C(

t). This yields

∪

C∈C(

C =

S. Therefore, for any C

, ..., C

, (it is not necessary that i = j

implies C

= C

,) if the set {C

, ..., C

} equals C(

M), then the sequence

, ..., C

is a closed compatible family of

M. It is easy to see that in case

of λ(S, X)=Y , each partial ﬁnite automaton in M(C

,...,C

)isaﬁnite

automaton whenever {C

, ..., C

} = C(

M). We use M

(

M)todenotethe

union set of all M(C

,...,C

), C

, ..., C

ranging over all sequences so that

the set {C

,...,C

} is equal to C(

M).

Theorem 6.2.1. If M = X, Y, S, δ, λ is an invertible ﬁnite automaton

with delay τ and λ(S, X)=Y, then the set of all inverse ﬁnite automata

with delay τ of M is ∪

M∈J (M,M



)

(

M) up to equivalence, i.e., for any

6.2 Inverses of a Finite Automaton 193

ﬁnite automaton M



= Y,X,S



,δ



,λ



,M



is an inverse with delay τ of

M, if and only if there exist

M in J (M,M



) and M



in M

(

M) such that



∼ M



Proof. only if : Suppose that M



is an inverse ﬁnite automaton with delay

τ of M.Intheproofoftheonly if part of Lemma 6.2.3, we construct a partial

ﬁnite automaton

M = Y, X,

δ,

λ in J (M, M



) such that

M and



are

equivalent, where



is the input restriction of M



by M . Especially, any

state S, s



 of



and the root state of

M corresponding to s



are equivalent;

any root state of

M is a root state of

M corresponding to s



for some state



in S



, and for any s



in S



there exists a root state of

M corresponding

to s



Let S



= {s



,...,s



} and

= {¯s | ¯s is a state of



,¯s ≺S, s



}, i =

1,...,h. Noticing that S



≺S, s



 and



(S, s



,y) ≺S, δ



,y),

using Lemma 6.1.1, it is easy to show that the sequence

,...,

is a closed

compatible family of



Let C

= {˜s | ˜s is a state of

M, there exists ¯s ∈

such that ˜s ∼ ¯s},

i =1,...,h. We prove that for any root state

t of

M and any i,1 i  h,

t is a root state of

M corresponding to s



,thenC(

t)=C

. Suppose that

t is a root state of

M corresponding to s



.Then

t is equivalent to the state

S, s



 of



. Therefore, for any ˜s ∈

S,˜s ∈ C(

t) if and only if ˜s ≺

t,ifand

only if ˜s ≺S, s



, if and only if there exists a state ¯s of



such that ˜s ∼ ¯s

and ¯s ≺S, s



, if and only if there exists ¯s in

such that ˜s ∼ ¯s,ifandonly

if ˜s ∈ C

. It follows that C(

t)=C

.Sinceforanys



in S



there exists a root

state of

M corresponding to s



,wehave{C

,...,C

}⊆C(

M). Since any

root state of

M is a root state of

M corresponding to s



for some state s



,wehaveC(

M) ⊆{C

,...,C

}.Thus{C

,...,C

} = C(

M). It follows

that C

,...,C

is a closed compatible family of

From

M ∼



,itiseasytoprovethat

= {¯s | ¯s is a state of



there exists ˜s ∈ C

such that ˜s ∼ ¯s}, i =1,...,h.Weprovethat



(

,y) ⊆

if and only if

δ(C

,y) ⊆ C

. Suppose



(

,y) ⊆

. For any ˜s ∈ C

,there

exists ¯s in

such that ˜s ∼ ¯s.When

δ(˜s, y) is deﬁned, from ˜s ∼ ¯s,



(¯s, y)is

deﬁned and

δ(˜s, y) ∼



(¯s, y). From



(

,y) ⊆

,wehave



(¯s, y) ∈

.It

follows that

δ(˜s, y) ∈ C

.Thus

δ(C

,y) ⊆ C

. Conversely, from the symmetry,

δ(C

,y) ⊆ C

implies



(

,y) ⊆

. We conclude that



(

,y) ⊆

if and

only if

δ(C

,y) ⊆ C

Construct



= Y,X,{¯c

,...,¯c



,where



(¯c

,y)=¯c



(¯c

,y)=



(S, s



,y),

i =1,...,h, y ∈ Y,