Tao R. Finite Automata and Application to Cryptography

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

1.2 Deﬁnitions of Finite Automata 11

(s, α)=λ

(s, xα



)=λ

(s, x)λ

(δ

(s, x),α



)

= λ

(ϕ(s),x)λ

(ϕ(δ

(s, x)),α



)

= λ

(ϕ(s),x)λ

(δ

(ϕ(s),x),α



)

= λ

(ϕ(s),xα



)=λ

(ϕ(s),α).

Therefore, (1.2) holds for any s in S

and any α in X

∗

of length n +1. We

conclude that (1.2) holds for any s in S

and any α in X

∗

.Thuss ∼ ϕ(s),

s ∈ S

.Sinceϕ is surjective, M

and M

are equivalent.

Conversely, if M

and M

are minimal and equivalent, and Y

= Y

,then

and M

are isomorphic. In fact, since M

and M

are equivalent, we have

= X

and for any state s in S

we can ﬁnd a state s



in S

with s ∼ s



.Let

ϕ be the relation ∼ from S

to S

.SinceM

is minimal, ϕ is single-valued.

Since M

and M

are equivalent, ϕ is a mapping from S

onto S

.Toprove

ϕ is one-to-one, suppose that ϕ(s

)=ϕ(s

). Since s

∼ ϕ(s

), i =1, 2, we

have s

∼ s

.SinceM

is minimal, this yields s

= s

.Thusϕ is one-to-one.

We conclude that ϕ is a one-to-one mapping from S

onto S

.Toprovethat

and M

are isomorphic, it is suﬃcient to prove that ϕ is an isomorphism.

Since s ∼ ϕ(s) holds for any s in S

, for any x in X

,wehave

(s, x)=λ

(ϕ(s),x)

and δ

,x) ∼ δ

(ϕ(s),x). The latter yields

ϕ(δ

,x)) = δ

(ϕ(s),x).

Therefore, ϕ is an isomorphism from M

to M

is called a ﬁnite subautomaton of M

, denoted by M

 M

,ifX

⊆

, Y

⊆ Y

, S

⊆ S

,and

(s, x)=δ

(s, x),λ

(s, x)=λ

(s, x),

s ∈ S

,x∈ X

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



of X and any nonempty subset S



of S,ifδ(S



)={δ(s, x) | s ∈ S



,x ∈



}⊆S



, S



is said to be closed with respect to X



in M. Clearly, given

, for any nonempty subset X

of X

, any nonempty subset S

of S

,and

any nonempty subset Y

of Y

,ifS

is closed with respect to X

in M

and

)={λ

(s, x) | s ∈ S

,x∈ X

}⊆Y

,then

X

,δ

×X

,λ

×X



is a ﬁnite subautomaton of M

For any states s and s



of a ﬁnite automaton X, Y, S, δ, λ, if there exists

x ∈ X such that s



= δ(s, x), s



is called a successor state of s;ifs



is a

successor state of s, s is called a predecessor state of s



12 1. Introduction

1.2.2 Special Finite Automata

We give deﬁnitions of several special ﬁnite automata.

Let M = X, Y, S, δ, λ be a ﬁnite automaton. If for any s in S, δ(s, x)

and λ(s, x) do not depend on x, M is said to be autonomous. We abbreviate

the autonomous ﬁnite automaton to a quadruple Y,S,δ,λ,whereδ is a

single-valued mapping from S to S,andλ is a single-valued mapping from S

to Y .

Example 1.2.2. Let Y = {0, 1} and S = {0, 1}

= {a

,...,a

|a

,...,a

0, 1}. Deﬁne

δ(a

,...,a

)=a

,...,a

,f(a

,...,a

),

λ(a

,...,a

)=g(a

,...,a

=0, 1,

where f and g are two single-valued mappings from {0, 1}

to {0, 1}.Then

Y,S,δ,λ is an autonomous ﬁnite automaton. We use BASR

f,g

to denote

the autonomous ﬁnite automaton. The name is an abbreviation of the phrase

“Binary Autonomous Shift Register with feedback function f and output

function g”.

Let M

= Y

,δ

,λ

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

is called an (autonomous) ﬁnite subautomaton of M

, denoted by M

 M

if Y

⊆ Y

, S

⊆ S

and

(s)=δ

(s),λ

(s)=λ

(s),

s ∈ S

For any autonomous ﬁnite automaton M = Y,S,δ, λ and any nonempty

subset S



of S,ifδ(S



)={δ(s) | s ∈ S



}⊆S, S



is said to be closed in

M. Clearly, given M

, for any nonempty subset S

of S

and any nonempty

subset Y

of Y

,ifS

is closed in M

and λ

)={λ

(s) | s ∈ S

}⊆Y

then Y

,δ

,λ

 is an autonomous ﬁnite subautomaton of M

For any single-valued mapping f from Y

× X

h+1

to Y ,whereh and k

are nonnegative integers, and X and Y are two nonempty ﬁnite sets, we use

to denote a ﬁnite automaton deﬁned by

= f(y

i−1

,...,y

i−k

,...,x

i−h

),i=0, 1,...

More precisely, M

= X, Y, Y

× X

,δ,λ,where

δ(y

−1

,...,y

−k

−1

,...,x

−h

,x

)

= y

−1

,...,y

−k+1

−1

,...,x

−h+1

,

1.2 Deﬁnitions of Finite Automata 13

λ(y

−1

,...,y

−k

−1

,...,x

−h

,x

)=y

= f(y

−1

,...,y

−k

−1

,...,x

−h

−1

,...,y

−k

∈ Y, x

−1

,...,x

−h

∈ X.

is called the (h, k)-order memory ﬁnite automaton determined by f.In

thecaseofk =0,M

is called the h-order input-memory ﬁnite automaton

determined by f.

Let f and g be single-valued mappings from Y

× U

p+1

× X

h+1

to Y

and U, respectively, where h and k are nonnegative integers, p  −1isan

integer, X, Y and U are nonempty ﬁnite sets. We use M

f,g

to denote a ﬁnite

automaton deﬁned by

= f(y

i−1

,...,y

i−k

,...,u

i−p

,...,x

i−h

i+1

= g(y

i−1

,...,y

i−k

,...,u

i−p

,...,x

i−h

i =0, 1,...

More precisely, M

f,g

= X, Y, Y

× U

p+1

× X

,δ,λ,where

δ(s, x

)=y

,...,y

−k+1

,...,u

−p+1

,...,x

−h+1

,

λ(s, x

)=y

= f(y

−1

,...,y

−k

,...,u

−p

,...,x

−h

= g(y

−1

,...,y

−k

,...,u

−p

,...,x

−h

s = y

−1

,...,y

−k

,...,u

−p

−1

,...,x

−h

∈Y

× U

p+1

× X

∈ X.

f,g

is called the (h, k, p)-order pseudo-memory ﬁnite automaton determined

by f and g. Clearly, in the case of p = −1, M

f,g

degenerates to M

Let M

= Y

,δ

,λ

 be an autonomous ﬁnite automaton, f asingle-

valued mapping from X

c+1

× λ

)toY .WeuseSIM(M

,f)todenotea

ﬁnite automaton X, Y, X

× S

,δ,λ,where

δ(x

−1

,...,x

−c

,x

)=x

−1

,...,x

−c+1

,δ

),

λ(x

−1

,...,x

−c

,x

)=f(x

−1

,...,x

−c

,λ

)),

−1

,...,x

−c

∈ X, s

∈ S

SIM(M

,f)isreferredtoasac-order semi-input-memory ﬁnite automaton

determined by M

and f.

Clearly, if f(x

,...,x

−c

,t) does not depend on t,thenSIM(M

,f)

degenerates to the input-memory ﬁnite automaton M



,wheref



,...,

−c

)=f(x

,...,x

−c

,t), t being an arbitrarily given element in λ

14 1. Introduction

A ﬁnite automaton X, Y, S, δ,λ is said to be linear over the ﬁnite ﬁeld

GF (q), if X, Y and S are vector spaces over GF (q) of dimensions l, m and n,

respectively, δ is a linear mapping from S ×X to S,andλ is a linear mapping

from S × X to Y ,wherel, m and n are some nonnegative integers.

InthecasewhereX, Y and S consist of all column vectors over GF (q)

of dimensions l, m and n, respectively, δ may be given by an n × n matrix A

and an n × l matrix B over GF (q), and λ may be given by an m × n matrix

C and an m × l matrix D over

GF (q), that is,

δ(s, x)=As + Bx,

λ(s, x)=Cs + Dx,

s ∈ S, x ∈ X.

The matrices A, B, C, D are called structure matrices of the ﬁnite automaton

and l, m, n structure parameters of the ﬁnite automaton. A is referred to as

the state transition matrix of the ﬁnite automaton. In the autonomous case,

its structure matrices are A, C and its structure parameters are m, n.

1.2.3 Compound Finite Automata

For any two ﬁnite automata M

= X

,δ

,λ

, i =1, 2withY

= X

we use C(M

)todenotethesuperpositionofM

and M

, i.e., the ﬁnite

automaton X

× S

,δ,λ,where

δ(s

,x)=δ

,x),δ

,λ

,x)),

λ(s

,x)=λ

,λ

,x)),

∈ S

,x∈ X

Another kind of combination of ﬁnite automata may be deﬁned as follows.

Let g be a single-valued mapping from U

×V

p+1

to U,andf a single-valued

mapping from W

t+1

to V . C



)=W, U, U

×W

p+t

,δ,λ is a (p+t, r)-

order memory ﬁnite automaton deﬁned by

= g(u

i−1

,...,u

i−r

,f(w

,...,w

i−t

),...,f(w

i−p

,...,w

i−p−t

)),

i =0, 1,...,

that is,

δ(u

−1

,...,u

−r

−1

,...,w

−p−t

,w

)

= u

,...,u

−r+1

,...,w

−p−t+1

,

λ(u

−1

,...,u

−r

−1

,...,w

−p−t

,w

)=u

= g(u

−1

,...,u

−r

,f(w

,...,w

−t

),...,f(w

−p

,...,w

−p−t

)),

−1

,...,w

−p−t

∈ W, u

−1

,...,u

−r

∈ U.

1.2 Deﬁnitions of Finite Automata 15

Theorem 1.2.1. Let s = u

−1

, ..., u

−r

−1

, ..., w

−p−t

 be a state of



).Lets

= w

−1

,...,w

−t

 and s

= u

−1

,...,u

−r

−1

,...,v

−p

,

where v

= f (w

,...,w

i−t

),i= −1, ..., −p. Then the state s

 of

C(M

) and s are equivalent. Moreover, if

−p

...v

−1

...= λ

(w

−p−1

,...,w

−p−t

,w

−p

...w

−1

...) (1.3)

and

...= λ

(u

−1

,...,u

−r

−1

,...,v

−p

,v

...), (1.4)

then

...= λ(u

−1

,...,u

−r

−1

,...,w

−p−t

,w

...), (1.5)

where λ

, λ

and λ are output functions of M

, M

and C



), respec-

tively.

Proof. Suppose that (1.3) and (1.4) hold. Then

= f(w

,...,w

i−t

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

and

= g(u

i−1

,...,u

i−r

,...,v

i−p

),i=0, 1,...

It immediately follows that

= g(u

i−1

,...,u

i−r

,f(w

,...,w

i−t

),...,f(w

i−p

,...,w

i−p−t

)),

i =0, 1,...

Thus (1.5) holds.

For any w

,... in W , suppose that

...= λ

,λ

...)).

Then there exist v

,... in V such that

...= λ

...).

It follows that

...= λ

...).

Therefore, (1.3) and (1.4) hold. From the result proven in the preceding

paragraph, (1.5) holds. Thus the state s

 of C(M

, M

) and the state

s of C



, M

)areequivalent. 

For n  1, we use C



,...,M

) to denote C



,...,

n−1

),M

), and C(M

, ..., M

) to denote C(C(M

,...,M

n−1

). For n =0,C



,...,M

)andC(M

,...,M

)meanM

. Clearly,



( M

, M

, ..., M

n−1

), M

)=C



, C



, ..., M

)), C(C(M

, M

..., M

n−1

), M

)=C(M

, C(M

, ..., M

)); that is, the associative law holds.

16 1. Introduction

1.2.4 Finite Automata as Recognizers

We have dealt with a ﬁnite automaton as a transducer which transforms an

input sequence to an output sequence of the same length.

We also deﬁned a special kind of ﬁnite automata, i.e., autonomous ﬁnite

automata. Behavior of an autonomous ﬁnite automaton is producing periodic

sequences.

In history, a ﬁnite automaton is considered as an event (sequence)

recognizer in the early 1950s by S. C. Kleene who introduced the concept

of regular events and proved the equivalence between regular events and

acceptable events by ﬁnite automata, an important result in formal language

theory. We review some basic concepts.

For a ﬁnite automaton X, Y, S, δ, λ,if|Y | =1,itiscalledaﬁnite

automaton without output, abbreviated to X, S, δ.

If X, S, δ is a ﬁnite automaton without output, s

∈ S and F ⊆ S,

the quintuple X,S, δ,s

,F is called a ﬁnite automaton recognizer,orﬁnite

recognizer for short. s

is called its initial state,andF its ﬁnal state set.

Let M = X, S, δ, s

,F be a ﬁnite automaton recognizer. The set

R(M)={α | α ∈ X

∗

,δ(s

,α) ∈ F } is called the recognizing set of M.

For any ﬁnite automaton recognizer M = X, S, δ,s

,F and any set

A ⊆ X

∗

,ifR(M)=A,wesaythatM recognizes A.

1.3 Linear Finite Automata

We review some properties of linear ﬁnite automata and the deﬁnition of the

z-transformation for linear ﬁnite automata.

Theorem 1.3.1. Let M be a linear ﬁnite automaton over GF (q) with

structure matrices A, B, C, D. For any s

in S and any x

,... in X, let

i+1

= δ(s

),y

= λ(s

),i=0, 1,... Then

= A

i−1



j=0

i−j−1

= CA



j=0

i−j

i =0, 1,...,

where H

= D, H

= CA

j−1

B, j>0.

Proof. We prove by induction on i that s

= A



i−1

j=0

i−j−1

holds

for any i  0. Basis : i = 0. It is trivial that s

= A



0−1

j=0

0−j−1

1.3 Linear Finite Automata 17

holds. Induction step : Suppose that s

= A



i−1

j=0

i−j−1

holds.

Then

i+1

= As

+ Bx

= A



i−1



j=0

i−j−1



+ Bx

= A

i+1



j=0

i−j

That is, s

i+1

= A

i+1



j=0

i−j

holds. Therefore, s

= A



i−1

j=0

i−j−1

holds for any i  0.

Using the proven result, for any i  0, we have

= Cs

+ Dx

= C



i−1



j=0

i−j−1



+ Dx

= CA

i−1



j=0

i−j−1

+ Dx

= CA



j=0

i−j

That is, y

= CA



j=0

i−j

holds for any i  0. 

Theorem 1.3.2. Let M = X, Y, S, δ, λ be a linear ﬁnite automaton over

GF (q) with structure matrices A, B, C, D. For any s

∈ S, any α

∈ X

, any

∈ GF (q),i=1, 2, we have

λ(c

+ c

)=c

λ(s

,α

)+c

λ(s

,α

Proof. For any inﬁnite sequence (ω-word) β, denote β =(β)

(β)

...,

where |(β)

| =1,i =0, 1,... From Theorem 1.3.1, we have

(λ(c

+ c

))

= CA

+ c



j=0

i−j

+ c

)

= CA

+ c



j=0

i−j

((c

)

+(c

)

= c

+ c



j=0

i−j

(α

)

+ c



j=0

i−j

(α

)

= c

(λ(s

,α

))

+ c

(λ(s

,α

))

i =0, 1,...

Thus λ(c

+ c

)=c

λ(s

,α

)+c

λ(s

,α

). 

From the proof of Theorem 1.3.2, we have the following corollaries.

18 1. Introduction

Corollary 1.3.1. Let M = X, Y, S, δ,λ be a linear ﬁnite automaton over

GF (q). For any positive integer k, any s

∈ S, any α

∈ X

∗

with |α

| = k,

any c

∈ GF (q),i=1, 2, we have

λ(c

+ c

)=c

λ(s

,α

)+c

λ(s

,α

Corollary 1.3.2. Let M = X, Y, S, δ,λ be a linear ﬁnite automaton over

GF (q). For any s ∈ S and any α ∈ X

, we have

λ(s, α)=λ(s, 0

)+λ(0,α),

where 0 stands for the zero vector in S, and 0

stands for an inﬁnite sequence

consisting of zero vectors in X.

λ(s, 0

) is called the free response of the state s,andλ(0,α)theforce

response of the input α. Corollary 1.3.2 means that any output sequence of

any linear ﬁnite automaton can be decomposed into the free response of the

initial state and the force response of the input sequence.

Clearly, all the free responses of a linear ﬁnite automaton over GF (q)is

a vector space over GF (q).

Theorem 1.3.3. Let M

= X

,δ

,λ

 be a linear ﬁnite automaton

over GF (q),i=1, 2,andX

= X

. For any s

∈ S

,i=1, 2,s

∼ s

if and

only if the zero state of M

and the zero state of M

are equivalent and the

free responses of s

and s

are the same.

Proof. Suppose that s

∼ s

. For any α ∈ X

,wethenhaveλ

,α)=

,α). Especially, taking α =0

,weobtainλ

, 0

)=λ

, 0

), that

is, the free responses of s

and s

are the same. Since λ

,α)=λ

, 0

)

+λ

(0,α), i =1, 2, λ

,α)=λ

,α) yields λ

(0,α)=λ

(0,α). It follows

that the zero state of M

and the zero state of M

are equivalent.

Conversely, suppose that the zero state of M

and the zero state of M

are equivalent and the free responses of s

and s

are the same. Then for

any α ∈ X

, λ

(0,α)=λ

(0,α), and λ

, 0

)=λ

, 0

). Thus for any

α ∈ X

, λ

,α)=λ

, 0

)+λ

(0,α)=λ

, 0

)+λ

(0,α)=λ

,α).

Therefore, s

∼ s

. 

Corollary 1.3.3. Let M be a linear ﬁnite automaton over GF (q). For any

states s

and s

of M, s

∼ s

if and only if the free responses of s

and s

are the same.

Corollary 1.3.4. Let M

and M

be two linear ﬁnite automata over GF (q).

Then M

∼ M

if and only if the zero state of M

and the zero state of M

areequivalentandthefreeresponsespacesofM

and M

are the same.

1.3 Linear Finite Automata 19

Corollary 1.3.5. Let M and M



be two linear ﬁnite automata over GF(q).

If the state s

of M and the state s



of M



are equivalent, i =1,...,k, then

for any c

in GF (q),i=1,...,k, the state c

+ ···+ c

of M and the

state c



+ ···+ c



of M



are equivalent.

Let M be a linear ﬁnite automaton over GF (q) with structure matrices

A, B, C, D and structure parameters l, m, n.Thematrix

⎡

⎢

⎣

n−1

⎤

⎥

⎦

is called the diagnostic matrix of M .

For any states s

and s

of M ,sinces

∼ s

if and only if their free

responses are the same, s

∼ s

if and only if CA

= CA

, i =0, 1,...

Since the degree of the minimal polynomial of A is at most n, s

∼ s

and only if CA

= CA

, i =0, 1,...,n− 1. Thus s

∼ s

if and only if

= K

Let T be a matrix consisting of some maximal independent rows of K

Then s

∼ s

if and only if Ts

= Ts

Theorem 1.3.4. Let M be a linear ﬁnite automaton over GF (q) with

structure matrices A, B, C, D. Assume that a matrix T over GF (q) satisﬁes

conditions: rows of T are linear independent and for any states s

and s

of M

∼ s

if and only if Ts

= Ts

.LetM



be a linear ﬁnite automaton over

GF (q) with structure matrices A



, where A



= TAR, B



= TB,



= CR, D



= D, R is a right inverse matrix of T .ThenM



is minimal

and equivalent to M.

Proof. Clearly, for any state s of M , Ts = T (RT s); therefore, s ∼ RT s.

We prove TART = TA. For any state s of M, the input 0 carries states

s and RT s to states As and ART s, respectively. From RT s ∼ s,wehave

ART s ∼ As. It follows that TARTs = TAs. From arbitrariness of s,wehave

TART = TA.

We prove CRT = C. For any state s of M,sinces ∼ RT s, the output of

the input 0 on the state s and the output of the input 0 on the state RT s are

the same, namely, Cs = CRTs. From arbitrariness of s,wehaveC = CRT.

For any state s of M, Ts is a state of M



.Weproves ∼ Ts. For any input

sequence x

..., let the output sequences on s and on Ts be y

... and



..., respectively. From Theorem 1.3.1, we have

= CA

s + Dx



j=1

i−j−1

20 1. Introduction



= C



i

Ts+ D





j=1



i−j−1



i =0, 1,...

Using TART = TA and CRT = C, this yields



=(CR)(TAR)

Ts+ Dx



j=1

(CR)(TAR)

i−j−1

(TB)x

=(CR)TA

s + Dx



j=1

(CR)TA

i−j−1

= CA

s + Dx



j=1

i−j−1

= y

i =0, 1,...

Thus s ∼ Ts.

Since for any state s



of M



there exists a state s of M such that s



= Ts,

we have s ∼ s



. On the other hand, for any state s of M,thestateTs of M



is equivalent to s.ThusM



and M are equivalent.

We prove that M



is minimal. Suppose that s



and s



are two equivalent

states of M



.Lets

= Rs



, i =1, 2. Then s

and Ts

(=s



)areequivalent,

i =1, 2. From s



∼ s



,wehaves

∼ s

. It follows that Ts

= Ts

.Thatis,



= s



.ThusM



is minimal. 

Let M

= X

,δ

,λ

, i =1, 2 be two linear ﬁnite automata over

GF (q). M

and M

are said to be similar, if there exists a linear isomorphism

from M

to M

. From the deﬁnition, it is easy to show that the similar relation

is reﬂexive, symmetric and transitive.

If M

and M

are minimal and equivalent, and Y

= Y

,thenM

and

are similar. In fact, it is proven in Subsect. 1.2.1 that the relation ∼ is

an isomorphism from M

to M

.Letϕ be the relation ∼ from S

to S

.We

prove that ϕ is linear. Let c

∈ GF (q), s

∈ S

, i =1, 2. Since s

∼ ϕ(s

i =1, 2, from Corollary 1.3.5, we have c

+ c

∼ c

ϕ(s

)+c

ϕ(s

). Thus

ϕ(c

)=c

ϕ(s

)+c

ϕ(s

). We conclude that M

and M

are similar.

Let f(z)=z

+ a

k−1

+ ···+ a

z + a

be a polynomial over GF (q).

We use P

f(z)

to denote the matrix

f(z)

⎡

⎢

⎣

01··· 00

00··· 00

00··· 01

−a

··· −a

k−2

−a

k−1

⎤

⎥

⎦

. (1.6)